Se dă un șir A, ale cărui elemente sunt definite prin relația \( {A}_{i} = {i}^{k} \cdot {2}^{i} \) pentru orice 1 ≤ i, unde K este un număr natural dat. Elementele acestui șir se așează într-o matrice M, formată din L linii și C coloane, astfel: \(M_{11}=A_{1}\), \(M_{21}=A_{2}\), \(M_{12}=A_{3}\), \(M_{31}=A_{4}\), \(M_{22}=A_{5}\), \(M_{13}=A_{6}\), \(M_{41}=A_{7}\), \(M_{32}=A_{8}\) …, adică parcurgând matricea pe diagonale din stânga-jos spre dreapta-sus.

De exemplu, pentru K=0, L=3 și C=4, șirul A este format din elementele 2, 4, 8, 16, 32, 64,..., iar matricea M va fi completată astfel:

Cerința

Ashima vă cere să răspundeți la Q cerințe de forma:

• \(l_1\ l_2\ c_1\ c_2\) : care este suma elementelor \(M_{i,j}\) din matricea M astfel încât \(l_1 \leq i\leq l_2\) și \( c_1 \leq j \leq c_2\)?

Date de intrare

Pe prima linie a fișierului de intrare ashima.in se află numerele K, L, C și Q, iar pe următoarele Q linii se află câte patru numere \(l_1\ l_2\ c_1\ c_2\).

Date de ieșire

Fișierul de ieșire ashima.out se vor afișa Q linii. Pe linia i se va afișa rezultatul celei de-a i-a cerințe, modulo 1.000.000.007.

Restricții și precizări

• 0 ≤ K ≤ 3
• 1 ≤ L, C ≤ 100.000
• 1 ≤ Q ≤ 200
• 1 ≤ l1 ≤ l2 ≤ L
• 1 ≤ c1 ≤ c2 ≤ C
• 0 ≤ l2 − l1, c2 − c1 ≤ 1.000
• Pentru 16 puncte, 1 ≤ L,C ≤ 100
• Pentru 21 puncte, 1 ≤ L,C ≤ 1.000
• Pentru 27 puncte, K = 0
• Pentru 15 puncte, K = 1
• Pentru 12 puncte, K = 2
• Pentru 9 puncte, K = 3

Exemplul 1:

ashima.in

0 3 4 3
1 1 2 4
1 2 1 3
1 3 2 3

ashima.out

584
366
1512

Explicație

Matricea M se completează ca în exemplul dat în enunț.

• La prima cerință trebuie calculată suma elementelor aflate între liniile 1 și 1 și coloanele 2 și 4. Suma acestor elemente este 8 + 64 + 512 = 584.
• La a doua cerință trebuie calculată suma elementelor aflate între liniile 1 și 2 și coloanele 1 și 3. Suma acestor elemente este 2 + 8 + 64 + 4 + 32 + 256 = 366.
• La a treia cerință trebuie calculată suma elementelor aflate între liniile 1 și 3 și coloanele 2 și 3. Suma acestor elemente este 8 + 64 + 32 + 256 + 128 + 1024 = 1512.

Exemplul 2:

ashima.in

1 2 5 2
1 1 2 4
1 2 1 3

ashima.out

1080
642

Explicație

Pentru al doilea exemplu avem K=1, deci șirul A are elementele \(1\cdot 2^{1}\), \(2\cdot 2^{2}\), \(3\cdot 2^{3}\), …,\(10\cdot 2^{10}\), iar matricea M, cu 2 linii și 5 coloane, se completează astfel:

La prima cerință trebuie calculată suma elementelor aflate între liniile 1 și 1 și coloanele 2 și 4. Suma acestor elemente este 24 + 160 + 896 = 1080. La a doua cerință trebuie calculată suma elementelor aflate între liniile 1 și 2 și coloanele 1 și 3. Suma acestor elemente este 2 + 24 + 160 + 8 + 64 + 384 = 642.