Să considerăm n zaruri, numerotate de la 1 la n. La aruncarea celor n zaruri obţinem o succesiune de n numere naturale cuprinse între 1 și 6. Suma unei aruncări va fi egală cu suma numerelor obţinute. Câte aruncări de n zaruri au suma cuprinsă între st și dr?

Cerința

Scrieți un program ce calculează răspunsul pentru mai multe întrebări de forma celei de mai sus. Pentru că numărul de aruncări poate fi destul de mare, calculați răspunsul modulo 1.000.003.

Date de intrare

Fișierul de intrare zaruri.in conţine pe prima linie numărul de întrebări q. Pe următoarele q linii se află parametrii ce definesc întrebările: triplete de numere naturale n st dr separate prin câte un spațiu.

Date de ieșire

Fișierul de ieșire zaruri.out va conţine q linii. Pe cea de a i-a linie va fi scris răspunsul la cea de a i-a întrebare din fişierul de intrare, modulo 1.000.003.

Restricții și precizări

• 1 ≤ n ≤ 3000
• 1 ≤ q ≤ 100.000
• 1 ≤ st ≤ dr ≤ 100.000
• Pentru 21 de puncte, 1 ≤ valoarea maximă pentru n < 10, 1 ≤ q < 10
• Pentru 42 de puncte, 10 ≤ valoarea maximă pentru n ≤ 600, 20 ≤ q ≤ 50000
• Pentru 27 de puncte, fără restricții suplimentare
• 10 puncte se acordă pentru testul din enunț

Exemplu:

zaruri.in

3
2 4 5
100 123 321
7 20 30

zaruri.out

7
97790
215259

Explicație

Pentru prima întrebare există două zaruri, numerotate 1 şi 2. Se cere să determinăm numărul de aruncări pentru care suma este cuprinsă între 4 şi 5 (deci suma aruncărilor poate fi 4 sau 5). Răspunsul pentru această întrebare este 7, cele 7 aruncări fiind: 1+3, 1+4, 2+2, 2+3, 3+1, 3+2, 4+1.