#include <algorithm>
#include <iostream>
#include <set>
#include <vector>
using namespace std;

bool is_seq_arithmetic(vector<long long> V) {
    sort( V.begin(), V.end() );
    long long D = V[1] - V[0];
    for (int i=0; i<int(V.size()); ++i) if (V[i] != V[0] + i*D) return false;
    return true;
}

int main() {
    vector<long long> ages(6);
    for (long long &x : ages) cin >> x;
    sort( ages.begin(), ages.end() );
    vector<long long> possible_differences = { ages[1] - ages[0], ages[2] - ages[1] };
    set<long long> answers;
    for (long long d : possible_differences) for (long long x : ages) for (long long add : vector<long long>{x-d,x+d}) if (add > 0) {
        vector<long long> new_ages = ages;
        new_ages.push_back(add);
        if (is_seq_arithmetic(new_ages)) answers.insert(add);
    }
    for (long long x : answers) cout << x << endl;
}

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

const long long MOD = 1000000007;

int main() {
    int N;
    cin >> N;
    vector<int> S(N);
    for (int &s : S) cin >> s;

    vector<int> cycle_count(N+1,0);
    vector<bool> seen(N,false);

    for (int n=0; n<N; ++n) if (!seen[n]) {
        seen[n] = true;
        int clen = 1, where = n;
        while (true) {
            where = S[where];
            if (seen[where]) break;
            seen[where] = true;
            ++clen;
        }
        ++cycle_count[clen];
    }

    long long answer = 1;

    for (int len=1; len<=N; ++len) if (cycle_count[len]>0) {
        int cnt = cycle_count[len];
        vector<int> groups;
        if (len%2) groups = {1,2,4}; else groups = {4};
        vector<long long> dp(cnt+1,0);
        dp[0] = 1;
        for (int c=1; c<=cnt; ++c) {
            for (int g : groups) if (g <= c) {
                long long curr = 1;
                for (int j=0; j<g-1; ++j) curr = (curr * (c-1-j)) % MOD;
                for (int j=0; j<g-1; ++j) curr = (curr * len) % MOD;
                dp[c] = (dp[c] + curr * dp[c-g]) % MOD;
            }
        }
        answer = (answer * dp[cnt]) % MOD;
    }
    cout << answer << endl;
}

#include <vector>
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <cmath>
using namespace std;

#define x first
#define y second
typedef std::pair<int,int> pii; typedef long long ll; typedef unsigned int ui; 

template <typename T, typename U> std::istream&operator>>(std::istream&i, pair<T,U>&p) {i >> p.x >> p.y; return i;}
template<typename T>std::istream&operator>>(std::istream&i,vector<T>&t) {for(auto&v:t){i>>v;}return i;}


constexpr double PI = 3.14159265358979323846;
template <typename T> struct Segment;

template <typename T> struct Point : public pair<T,T> {
    using pair<T,T>::x;
    using pair<T,T>::y;

    Point(T a=0,T b=0) : pair<T,T>(a,b) {}
    Point(const pair<T,T> &p) : pair<T,T>(p.x,p.y) {}
    Point(const Point<T>&p) = default;
    Point<T>& operator=(const Point<T>&p) = default;

    Point<T>& operator-=(const Point<T>&p) { x -= p.x; y -= p.y; return *this; }
    Point<T>& operator+=(const Point<T>&p) { x += p.x; y += p.y; return *this; }
    Point<T>& operator*=(T f) { x *= f; y *= f; return *this; }
    Point<T> operator-(const Point<T>&p) const { Point<T> t(*this); t -= p; return t; }
    Point<T> operator+(const Point<T>&p) const { Point<T> t(*this); t += p; return t; }
    Point<T> operator*(T f) const { Point<T> t(*this); t *= f; return t; }

    T squaredDistance(const Point<T>&o) const { return Segment<T>{*this,o}.squaredLength(); }
    long double distance(const Point<T>&o) const { return Segment<T>{*this,o}.length(); }
};

// >0 left turn, <0 right turn, =0 straight
template <typename T> T ccw(const Point<T>&a, const Point<T>&b, const Point<T>&c) { return (b.x-a.x)*(c.y-a.y) - (b.y-a.y)*(c.x-a.x); }
template <typename T> double cosangle(const Point<T>&a, const Point<T> &b, const Point<T> &c) {
    return (double)((b.x-a.x)*(c.x-a.x) + (b.y-a.y)*(c.y-a.y)) / a.distance(b) / a.distance(c);
}

template <typename T> double angle(const Point<T>&a, const Point<T> &b, const Point<T> &c) {
    return acos(cosangle(a,b,c));
}
template <typename T> int orientation(const Point<T>&a, const Point<T>&b, const Point<T>&c) { auto o = ccw(a,b,c); return (o>1e-6)-(o<-1e-6); }

template <typename T> struct Segment : public pair<Point<T>,Point<T>> {
    using pair<Point<T>,Point<T>>::x;
    using pair<Point<T>,Point<T>>::y;
    explicit Segment(Point<T> a={0,0}, Point<T> b={0,0}) : pair<Point<T>,Point<T>>(a,b) {}
    Segment(const Segment<T>&) = default;
    Segment<T>& operator=(const Segment<T>&) = default;
    inline T dx() const { return x.x - y.x; }
    inline T dy() const { return x.y - y.y; }
    T squaredLength() const { return dx()*dx()+dy()*dy(); }
    long double length() const { return sqrtl(squaredLength()); }
};

template <typename T> struct Polygon : public vector<Point<T>> {
    using vector<Point<T>>::vector;
    using vector<Point<T>>::at;
    using vector<Point<T>>::front;
    using vector<Point<T>>::back;

    T doubleSignedArea() const {
        if (this->empty()) return T(0);
        T area = back().x*front().y - back().y*front().x;
        for (int i = 0; i < this->size()-1; ++i) area += (at(i).x * at(i+1).y - at(i+1).x * at(i).y);
        return area;
    }

    double circumference() const {
        if (this->empty()) return T(0);
        T res = back().distance(front());
        for (int i = 0; i < this->size()-1; ++i) res += at(i).distance(at(i+1));
        return res;
    }
};

template <typename T> Polygon<T> convexhull(const vector<Point<T>> &v) {
    ui N = (ui)v.size(); vector<Point<T>> w(N+1); int lo = 0;
    for (int i = 0; i<N; ++i) if (v[i].y < v[lo].y || (v[i].y == v[lo].y && v[i].x < v[lo].x)) lo = i;
    Point<T> o = v[lo];
    for (int i = 0; i<N; ++i) w[i+1] = {v[i].x-o.x,v[i].y-o.y};
    swap(w[1],w[lo+1]);

    sort(w.begin()+2,w.end(),[](Point<T>&a,Point<T>&b) {
        if (a.y==0) return b.y != 0 || a.x < b.x;
        if (b.y==0) return false;
        auto disc = (a.x*b.y-a.y*b.x);
        return disc > 0 || (disc == 0 && a.y < b.y);
    });
    w[0] = w[N];
    ui M=1;
    for (int i=2;i<=N;++i) {
        while(ccw(w[M-1],w[M],w[i]) <= 0) if (M>1) --M; else if (i == N) break; else ++i;
        ++M; swap(w[M],w[i]);
    }
    Polygon<T> res(M);
    for (int i=0;i<M;++i) res[i] = {w[i+1].x+o.x,w[i+1].y+o.y};
    return res;
}



#define next(x) (x==M-1?0:x+1)

class Inexact {
public:

    void solve(istream& cin, ostream& cout) {
        int N, W, H; cin >> N >> W >> H;
        vector<Point<ll>> A(N); cin >> A;
        auto Poly = convexhull(A);
        if (Poly.size() <= 2) {
            cout << 0 << '\n';
            return;
        }
        int M = Poly.size();

        vector<Point<double>> DPoly;
        for (int i = 0; i < M; ++i) DPoly.emplace_back(Poly[i].x, Poly[i].y);

        double ans = PI;

        Point<ll> Orig{0,0};
        for (int flip = 0; flip < 2; ++flip) {
            for (int rot = 0; rot < 4; ++rot) {
                int L = 0, R = 0;
                for (int i = 0; i < M; ++i) {
                    if (ccw(Orig, Poly[L], Poly[i]) > 0) L = i;
                    if (ccw(Orig, Poly[R], Poly[i]) < 0) R = i;
                }

                ans = min(ans, angle(Orig, Poly[L], Poly[R]));

                while (true) {
                    if (Poly[L].y <= Poly[next(L)].y) break; // no x-intercept

                    ll num = Poly[L].y * Poly[next(L)].x - Poly[L].x * Poly[next(L)].y;
                    ll den = Poly[L].y - Poly[next(L)].y;

                    Point<double> intercept{double(num)/den, 0};
                    if (intercept.x >= W) break;

                    // find the right-most point from intercept
                    while (true) {
                        if (orientation(intercept, DPoly[R], DPoly[next(R)]) == -1) {
                            R = next(R);
                        } else {
                            break;
                        }
                    }

                    // find whether the angle L/Intercept/R is <= 45 degrees
                    ans = min(ans, angle(intercept, DPoly[L], DPoly[R]));
                    L = next(L);
                }

                swap(W, H);
                for (auto &a: Poly) { swap(a.x, a.y); a.y = H - a.y; }
                for (auto &a: DPoly) { swap(a.x, a.y); a.y = H - a.y; }
            }

            for (auto &a: Poly) a.x = W - a.x;
            for (auto &a: DPoly) a.x = W - a.x;
            reverse(Poly.begin(),Poly.end());
            reverse(DPoly.begin(),DPoly.end());
        }

        cout << fixed << setprecision(10) << ans * 180.0 / PI << '\n';
    }
};


int main() {
	ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	Inexact solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int main() {
  int n; cin >> n;
  vector<int> v;
  copy_n(istream_iterator<int>(cin), n, back_inserter(v));
  bool ok = false;
  for (int i=0; i<n; ++i) {
    auto w = v; // make a copy
    rotate(w.begin(), w.begin()+i, w.end());
    ok |= is_sorted(w.begin(), w.end());
  }
  cout << (ok ? "Phew\n" : "Lie\n");
}

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    scanf("%d", &n);
    
    for(int i=0; i<n; i++) printf("%c", 'a');
    for(int i=0; i<n; i++) printf("%c", 'b');
    printf("\n");

    for(int i=0; i<n-1; i++) printf("%c", 'a');
    printf("%c", 'b');
    printf("%c", 'a');
    for(int i=0; i<n-1; i++) printf("%c", 'b');
    printf("\n");

    return 0;
}

#include <iostream>
using namespace std;
#define int int64_t

struct rectangle {
  int x1, y1, x2, y2;
  int area() const { return (x2-x1)*(y2-y1); }
};
istream& operator>>(istream& is, rectangle& r) {
  return is >> r.x1 >> r.y1 >> r.x2 >> r.y2;
}

signed main() {
  int t; cin >> t;
  while (t--) {
    rectangle a, b;
    cin >> a >> b;
    int w = min(a.x2, b.x2) - max(a.x1, b.x1);
    int h = min(a.y2, b.y2) - max(a.y1, b.y1);
    int best = max(a.area(), b.area());
    if (w >= 0 && h >= 0) {
      best = max(best, rectangle{0, min(a.y1, b.y1),
                                   w, max(a.y2, b.y2)}.area());
      best = max(best, rectangle{0, min(a.x1, b.x1),
                                   h, max(a.x2, b.x2)}.area());
    }
    cout << best << '\n';
  }
}

/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author majk
 */

#ifndef MAJK_LIB
#define MAJK_LIB

#include <vector>
#include <stack>
#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <iomanip>
#include <set>
#include <functional>
#include <algorithm>
#include <numeric>
#include <cassert>
#include <cmath>
#include <string>
#include <queue>
#include <array>
#include <bitset>
using namespace std;

#define x first
#define y second
typedef std::pair<int,int> pii; typedef long long ll; typedef unsigned long long ull; typedef unsigned int ui; typedef pair<ui,ui> puu;

template <typename T, typename U> std::istream&operator>>(std::istream&i, pair<T,U>&p) {i >> p.x >> p.y; return i;}
template<typename T>std::istream&operator>>(std::istream&i,vector<T>&t) {for(auto&v:t){i>>v;}return i;}
template <typename T, typename U> std::ostream&operator<<(std::ostream&o, const pair<T,U>&p) {o << p.x << ' ' << p.y; return o;}
template<typename T>std::ostream&operator<<(std::ostream&o,const vector<T>&t) {if(t.empty())o<<'\n';for(size_t i=0;i<t.size();++i){o<<t[i]<<" \n"[i == t.size()-1];}return o;}
template<typename T> using minheap = priority_queue<T, vector<T>, greater<T>>;
template<typename T> using maxheap = priority_queue<T, vector<T>, less<T>>;
ui logceil(ll x) { return x?8*sizeof(ll)-__builtin_clzll(x):0; }

namespace std { template<typename T,typename U>struct hash<pair<T,U>>{hash<T>t;hash<U>u;size_t operator()(const pair<T,U>&p)const{return t(p.x)^(u(p.y)<<7);}}; }
template<typename T,typename F>T bsh(T l,T h,const F&f){T r=-1,m;while(l<=h){m=(l+h)/2;if(f(m)){l=m+1;r=m;}else{h=m-1;}}return r;}
template<typename F> double bshd(double l,double h,const F&f,double p=1e-9){ui r=3+(ui)log2((h-l)/p);while(r--){double m=(l+h)/2;if(f(m)){l=m;}else{h=m;}}return (l+h)/2;}
template<typename T,typename F>T bsl(T l,T h,const F&f){T r=-1,m;while(l<=h){m=(l+h)/2;if(f(m)){h=m-1;r=m;}else{l=m+1;}}return r;}
template<typename F> double bsld(double l,double h,const F&f,double p=1e-9){ui r=3+(ui)log2((h-l)/p);while(r--){double m=(l+h)/2;if(f(m)){h=m;}else{l=m;}}return (l+h)/2;}
template<typename T> T gcd(T a,T b) { if (a<b) swap(a,b); return b?gcd(b,a%b):a; }


template<typename T>class vector2:public vector<vector<T>>{public:vector2(){} vector2(size_t a,size_t b,T t=T()):vector<vector<T>>(a,vector<T>(b,t)){}};
template<typename T>class vector3:public vector<vector2<T>>{public:vector3(){} vector3(size_t a,size_t b,size_t c,T t=T()):vector<vector2<T>>(a,vector2<T>(b,c,t)){}};
template<typename T>class vector4:public vector<vector3<T>>{public:vector4(){} vector4(size_t a,size_t b,size_t c,size_t d,T t=T()):vector<vector3<T>>(a,vector3<T>(b,c,d,t)){}};
template<typename T>class vector5:public vector<vector4<T>>{public:vector5(){} vector5(size_t a,size_t b,size_t c,size_t d,size_t e,T t=T()):vector<vector4<T>>(a,vector4<T>(b,c,d,e,t)){}};


#endif

class averaging {
public:
    void solve(istream& cin, ostream& cout) {
        int N, K; cin >> N >> K;
        vector<int> A(N); cin >> A;
        int tot = 0;
        for (int a: A) tot += a;
        vector5<bool> D(N+1, N+1, N+1, 101, 101, false);
        D[0][0][0][0][0] = true;
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j <= i; ++j) {
                for (int k = 0; k <= i; ++k) {
                    for (int l = 0; l <= 100; ++l) {
                        for (int m = 0; m <= 100; ++m) {
                            if (D[i][j][k][l][m]) {
                                D[i+1][j+1][k][l+A[i]][m] = true;
                                D[i+1][j][k+1][l][m+A[i]] = true;
                                D[i+1][j][k][l][m] = true;
                            }
                        }
                    }
                }
            }
        }

        pii best = {0, 1};
        pii diff = {K, 1};
        for (int i = 1; i < N; ++i) {
            for (int j = 1; j < N; ++j) {
                int k = N - i - j;
                if (k > 0) {
                    for (int l = 1; l < 100; ++l) {
                        for (int m = 1; m < 100; ++m) {
                            int n = tot - l - m;
                            if (D[N][i][j][l][m]) {
                                int den = i*j*k*3;
                                int num = j*k*l + i*k*m + i*j*n;
                                int numDiff = abs(num - K*i*j*k*3);
                                if (numDiff * diff.y < den * diff.x) {
                                    diff = {numDiff, den};
                                    best = {num, den};
                                } else if (numDiff * diff.y == den * diff.x && num < K*i*j*k*3) {
                                    diff = {numDiff, den};
                                    best = {num, den};
                                }
                            }
                        }
                    }
                }
            }
        }

        int g = gcd(best.x, best.y);
        cout << best.x / g << '/' << best.y / g << endl;
    }
};


int main() {
	ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	averaging solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
    return 0;
}

#include <algorithm>
#include <iostream>
#include <map>
#include <string>
using namespace std;

int main() {
    int W;
    cin >> W;
    map< string, string > wordlist;
    for (int w=0; w<W; ++w) {
        string word;
        cin >> word;
        string sorted_word = word;
        sort( sorted_word.begin(), sorted_word.end() );
        if (wordlist.count(sorted_word) == 0) wordlist[sorted_word] = word;
    }

    int Q;
    cin >> Q;
    for (int q=0; q<Q; ++q) {
        string query;
        cin >> query;
        sort( query.begin(), query.end() );
        string answer = "";
        for (int subset = 1; subset < (1<<9); ++subset) {
            string used = "";
            for (int i=0; i<9; ++i) if (subset & 1<<i) used += query[i];
            if (wordlist.count(used) == 0) continue;
            if (used.size() < answer.size()) continue;
            if (used.size() > answer.size()) { answer = wordlist[used]; continue; }
            answer = min( answer, wordlist[used] );
        }
        if (answer == "") answer = "IMPOSSIBLE";
        cout << answer << "\n";
    }
}

#include <vector>
#include <iostream>
#include <map>
#include <algorithm>
using namespace std;

typedef long long ll; 

class die {
public:
    void solve(istream& cin, ostream& cout) {
        vector<int> A(6); cin >> A;
        ll S; cin >> S;
        int Q; cin >> Q;
        --Q;
        S -= A[Q];

        vector<int> M(3, 0);
        for (int i = 0; i < 3; ++i) {
            for (int j = 0; j < 6; ++j) {
                int k = min(j, 5-j);
                if (i != k) {
                    M[i] |= 1<<(3*A[j]+k-3);
                }
            }
        }

        map<int, int> C;
        vector<int> D{0};
        C[0] = 0;
        int cur = 0, id = 0;
        while (true) {
            int next = (cur&((1<<27)-1))<<3;
            for (int i = 0; i < 3; ++i) {
                if ((cur & M[i]) != M[i]) next |= 1<<i;
            }
            cur = next;
            D.push_back(cur);
            auto it = C.find(cur);
            if (it != C.end()) break;

            C[cur] = ++id;
        }

        int prep = C[cur];
        int per = id + 1 - C[cur];
        
        if (S > prep) S = (S - prep) % per + prep;

        if ((D[S]>>min(Q,5-Q))&1) cout << "ADA" << '\n';
        else cout << "BOB" << '\n';
    }
};


int main() {
	ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	die solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
    return 0;
}

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int N;
vector< vector<int> > G;
vector<bool> visited;
vector< vector<int> > solution;
bool OK;

bool dfs(int v) {
    visited[v] = true;
    vector<int> unmatched_children;
    for (int x : G[v]) if (!visited[x]) if (!dfs(x)) unmatched_children.push_back(x);
    while (unmatched_children.size() >= 2u) {
        int a = unmatched_children.back();
        unmatched_children.pop_back();
        int b = unmatched_children.back();
        unmatched_children.pop_back();
        solution.push_back( {a,b,v} );
    }
    if (unmatched_children.empty()) return false;
    solution.push_back( {unmatched_children[0], v, -1} );
    return true;
}

int main() {
    cin >> N;
    G.resize(2*N);
    int F;
    cin >> F;
    while (F--) {
        int x, y;
        cin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    OK = true;
    visited.resize(2*N,false);
    for (int n=0; n<2*N; ++n) if (!visited[n]) if (!dfs(n)) OK = false;
    cout << (OK ? "POSSIBLE\n" : "IMPOSSIBLE\n");
    if (OK) for (auto row : solution) cout << row[0] << " " << row[1] << " " << row[2] << "\n";
}

N = int(input())
A, B = map(int, input().split())

best_k = 2000
for i in range(0, N+1):
    for j in range(0, N+1):
        if (i * A + j * B) % N != 0: continue
        if i + j == 0: continue
        best_k = min(best_k, i+j)
print(best_k)        

#include <vector>
#include <iostream>
using namespace std;

#define x first
#define y second
typedef std::pair<int,int> pii; typedef long long ll; typedef unsigned long long ull; typedef unsigned int ui; typedef pair<ui,ui> puu;

template<typename T>class vector2:public vector<vector<T>>{public:vector2(){} vector2(size_t a,size_t b,T t=T()):vector<vector<T>>(a,vector<T>(b,t)){}};


template <unsigned int N> class Field {
    typedef unsigned int ui;
    typedef unsigned long long ull;
	inline ui pow(ui a, ui p){ui r=1,e=a;while(p){if(p&1){r=((ull)r*e)%N;}e=((ull)e*e)%N;p>>=1;}return r;}
	inline ui inv(ui a){return pow(a,N-2);}
public:
    inline Field(int x = 0) : v(x) {}
	inline Field<N> pow(int p){return (*this)^p; }
	inline Field<N> operator^(int p){return {(int)pow(v,(ui)p)};}
    inline Field<N>&operator+=(const Field<N>&o) {if (v+o.v >= N) v += o.v - N; else v += o.v; return *this; }
    inline Field<N>&operator-=(const Field<N>&o) {if (v<o.v) v -= o.v-N; else v-=o.v; return *this; }
    inline Field<N>&operator*=(const Field<N>&o) {v=(ull)v*o.v % N; return *this; }
    inline Field<N>&operator/=(const Field<N>&o) { return *this*=inv(o.v); }
    inline Field<N> operator+(const Field<N>&o) const {Field<N>r{*this};return r+=o;}
    inline Field<N> operator-(const Field<N>&o) const {Field<N>r{*this};return r-=o;}
    inline Field<N> operator*(const Field<N>&o) const {Field<N>r{*this};return r*=o;}
    inline Field<N> operator/(const Field<N>&o) const {Field<N>r{*this};return r/=o;}
    inline Field<N> operator-() {if(v) return {(int)(N-v)}; else return {0};};
    inline Field<N>& operator++() { ++v; if (v==N) v=0; return *this; }
    inline Field<N> operator++(int) { Field<N>r{*this}; ++*this; return r; }
    inline Field<N>& operator--() { --v; if (v==-1) v=N-1; return *this; }
    inline Field<N> operator--(int) { Field<N>r{*this}; --*this; return r; }
    inline bool operator==(const Field<N>&o) const { return o.v==v; }
	inline bool operator!=(const Field<N>&o) const { return o.v!=v; }
	inline explicit operator ui() const { return v; }
	inline static vector<Field<N>>fact(int t){vector<Field<N>>F(t+1,1);for(int i=2;i<=t;++i){F[i]=F[i-1]*i;}return F;}
	inline static vector<Field<N>>invfact(int t){vector<Field<N>>F(t+1,1);Field<N> X{1};for(int i=2;i<=t;++i){X=X*i;}F[t]=1/X;for(int i=t-1;i>=2;--i){F[i]=F[i+1]*(i+1);}return F;}
private: ui v;
};
template<unsigned int N>istream &operator>>(std::istream&is,Field<N>&f){unsigned int v;is>>v;f=v;return is;}
template<unsigned int N>ostream &operator<<(std::ostream&os,const Field<N>&f){return os<<(unsigned int)f;}
template<unsigned int N>Field<N> operator+(int i,const Field<N>&f){return Field<N>(i)+f;}
template<unsigned int N>Field<N> operator-(int i,const Field<N>&f){return Field<N>(i)-f;}
template<unsigned int N>Field<N> operator*(int i,const Field<N>&f){return Field<N>(i)*f;}
template<unsigned int N>Field<N> operator/(int i,const Field<N>&f){return Field<N>(i)/f;}

typedef Field<1000000007> FieldMod;

class treequeries {
public:
    void solve(istream& cin, ostream& cout) {
        int Q; cin >> Q;
        vector<FieldMod> B(31, 0);
        vector2<int> C(31, 31, 0);
        for (int i = 0; i <= 30; ++i) {
            C[i][0] = C[i][i] = 1;
            for (int j = 1; j < i; ++j) C[i][j] = C[i-1][j-1] + C[i-1][j];
        }
        auto add = [&](int x, FieldMod s) {
            int pref = 0, cnt = 0;
            for (int i = 30; i >= 0; --i) {
                if (x&1<<i) {
                    for (int j = 0; j <= i; ++j) B[cnt+j] += s * C[i][j];

                    pref |= 1<<i;
                    cnt++;
                }
            }
        };

        for (int q = 0; q < Q; ++q) {
            int t, l, r; cin >> t >> l >> r;
            if (t == 0) {
                FieldMod X; cin >> X;
                add(r, X);
                add(l, -X);
            } else {
                FieldMod ans = 0;
                for (int i = 31-r; i < 31-l; ++i) ans += B[i];
                cout << ans << '\n';
            }
        }
    }
};

int main() {
	ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	treequeries solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
    return 0;
}