Postată de	Clasa	Intrare/ieșire	Limită timp	Limită memorie	Sursa problemei	Autor	Dificultate
Iacob Tudor (IacobTudor)	10	biti.in / biti.out	0.5 secunde	64 MB / 8 MB	infoleague.net runda antrenament 2, problema D.	Tudor Iacob	concurs

Cerința

Se dă N și Q, apoi Q interogări de tipul K X pentru fiecare interogare să se afișeze separate prin spațiu ( ficare interogare pe un rând diferit ):

1. Câți vectori de exact N elemente din intervalul \([0, {2}^{K})\) ( mai mari sau egale cu \(0\) și strict mai mici ca \({2}^{K}\) ) există astfel încât valoarea \(a_1\) & \(a_2\) & ... & \(a_N\) să fie X-frumoasă. Un număr este X-frumos dacă în reprezentare binară are exat X biți setați ( cu valoare = 1 ). Cu & am notat operația pe biți AND.

2. Câți vectori de exact N elemente din intervalul \([0, {2}^{K})\) ( mai mari sau egale cu \(0\) și strict mai mici ca \({2}^{K}\) ) există astfel încât valoarea \(a_1\) | \(a_2\) | ... | \(a_N\) să fie X-frumoasă. Un număr este X-frumos dacă în reprezentare binară are exat X biți setați ( cu valoare = 1 ). Cu | am notat operația pe biți OR.

3.Câți vectori de exact N elemente din intervalul \([0, {2}^{K})\) ( mai mari sau egale cu \(0\) și strict mai mici ca \({2}^{K}\) ) există astfel încât valoarea \(a_1\) ^ \(a_2\) ^ ... ^ \(a_N\) să fie X-frumoasă. Un număr este X-frumos dacă în reprezentare binară are exat X biți setați ( cu valoare = 1 ). Cu ^ am notat operația pe biți XOR.

Date de intrare

Fișierul de intrare bit.in va conține pe prima linie N și Q iar apoi pe urmatoarele Q linii câte 2 numere, K și X, cu semnificația din enunț.

Date de ieșire

Fișierul de ieșire biti.out va conține pe Q linii răspunsul întrebărilor, pe linia i se va afla răspunsul aferent celei de a i-a intergoare după ordinea citirii.

Restricții și precizări

1 <= N <= 1.000.000.000.
1 <= Q <= 100.000.
0 <= X <= K <= 1.000.000.
Toate rezultatele vor fi tipărite modulo \({10}^{9}+7\).

Exemplu:

biti.in

2 1
1 1

biti.out

1 3 2