zaruri

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ță

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 \leq n \leq 3 \ 000$;
• $1 \leq q \leq 10^5$;
• $1 \leq st \leq dr \leq 10^5$;

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$.