monede2 100p

#include <bits/stdc++.h>

using namespace std;

struct Raport {
    int a, b;
    Raport(int, int);
    Raport();

    Raport& operator+=(const Raport&);
    Raport& operator-=(const Raport&);
    Raport& operator*=(const Raport&);
    Raport& operator/=(const Raport&);

    bool operator==(const Raport& rhs) const;
    bool operator!=(const Raport& rhs) const;
};

Raport operator+(Raport, const Raport&);
Raport operator-(Raport, const Raport&);
Raport operator*(Raport, const Raport&);
Raport operator/(Raport, const Raport&);

Raport::Raport(int A, int B) : a(A), b(B) {}

Raport::Raport() : Raport(0, 1) {}

Raport& Raport::operator+=(const Raport& rhs) {
    a = ((long long)a * rhs.b + (long long)b * rhs.a) % 1000000007;
    b = ((long long)b * rhs.b) % 1000000007;
    return *this;
}

Raport& Raport::operator-=(const Raport& rhs) {
    a = ((long long)a * rhs.b - (long long)b * rhs.a) % 1000000007;
    if (a < 0)
        a += 1000000007;
    b = ((long long)b * rhs.b) % 1000000007;
    return *this;
}

Raport& Raport::operator*=(const Raport& rhs) {
    a = ((long long)a * rhs.a) % 1000000007;
    b = ((long long)b * rhs.b) % 1000000007;
    return *this;
}

Raport& Raport::operator/=(const Raport& rhs) {
    a = ((long long)a * rhs.b) % 1000000007;
    b = ((long long)b * rhs.a) % 1000000007;
    return *this;
}

bool Raport::operator==(const Raport& rhs) const {
    return ((long long)a * rhs.b - (long long)b * rhs.a) % 1000000007 == 0;
}

bool Raport::operator!=(const Raport& rhs) const { return !(*this == rhs); }

Raport operator+(Raport a, const Raport& b) { return a += b; }

Raport operator-(Raport a, const Raport& b) { return a -= b; }

Raport operator*(Raport a, const Raport& b) { return a *= b; }

Raport operator/(Raport a, const Raport& b) { return a /= b; }


class InParser {
private:
    FILE* fin;
    char* buff;
    int sp;
    char read_ch() {
        ++sp;
        if (sp == 16384) {
            sp = 0;
            fread(buff, 1, 16384, fin);
        }
        return buff[sp];
    }
public:
    InParser(const char* nume) {
        fin = fopen(nume, "r");
        buff = new char[16384]();
        sp = 16383;
    }

    InParser& operator >> (int& n) {
        char c;
        while (!isdigit(c = read_ch()));
        n = c - '0';
        while (isdigit(c = read_ch()))
            n = 10 * n + c - '0';
        return *this;
    }
};
class OutParser {
private:
    FILE* fout;
    char* buff;
    int sp;
    void write_ch(char ch) {
        if (sp == 50000) {
            fwrite(buff, 1, 50000, fout);
            sp = 0;
        }
        buff[sp++] = ch;
    }
public:
    OutParser(const char* name) {
        fout = fopen(name, "w");
        buff = new char[50000]();
        sp = 0;
    }
    ~OutParser() {
        fwrite(buff, 1, sp, fout);
        fclose(fout);
    }
    OutParser& operator << (int n) {
        if(n < 10)
            write_ch(n + '0');
        else {
            (*this) << (n / 10);
            write_ch(n % 10 + '0');
        }
        return *this;

    }
    OutParser& operator << (const char& ch) {
        write_ch(ch);
        return *this;
    }
};

inline Raport Merge(const Raport& a, const Raport& b) {
    return a + b - Raport(2, 1) * a * b;
}

int main() {
    InParser fin("monede2.in");
    OutParser fout("monede2.out");
    Raport Tree[1 << 21];
    int N, Q, x, y;
    fin >> N >> Q;
    for(int i = 0; i < N; i++) {
        fin >> x >> y;
        Tree[N + i] = {x, y};
    }
    for(int i = N - 1; i; i--)
        Tree[i] = Merge(Tree[i << 1], Tree[i << 1 | 1]);
    while(Q--) {
        fin >> x >> y;
        x += N - 1, y += N - 1;
        Raport R(0, 1);
        while(x <= y) {
            if(x & 1) {
                R = Merge(R, Tree[x]);
                ++x;
            }
            if(!(y & 1)) {
                R = Merge(R, Tree[y]);
                --y;
            }
            x >>= 1, y >>= 1;
        }
        fout << R.a << ' ' << R.b << '\n';
    }
}