RoAlgo Educational Round #3 | P4(😐🤣☠️)

Un vector $a$ se numește 😐🤣☠️ dacă oricum am alege 2 indici $i$ și $j$, $i \leq j$, atunci toate valorile naturale cuprinse în intervalul numeric $[\min(a_i, \dots, a_j), \max(a_i, \dots, a_j)]$ apar măcar odată printre numerele $a_i,\dots,a_j$.

Cerință

Pentru $n$ și $m$ calculați câți vectori 😐🤣☠️ cu $n$ elemente există, cu condiția că $1 \leq a_i \leq m$.

Date de intrare

Pe prima linie veți citi $t$, numărul de test cases. Pe următoarele $t$ linii se vor afla 2 numere, $n$ și $m$.

Date de ieșire

Se vor afișa $t$ linii, fiecare reprezentând răspunsul pentru fiecare test case în parte.

Restricții și precizări

• Răspunsul se va calcula modulo $10^9 + 7$.
• $1 \leq t \leq 100$
• $1 \leq n \leq 10^{18}$
• $1 \leq m \leq 200$
• Se garantează faptul că suma $m$-urilor pe toate test case-urile nu depășește $300$.

Exemplu

stdin

7
2 2
3 1
5 10
5 100
134114 12
1000000 90
24912491 34

stdout

4
1
664
7954
437298534
70485274
125184942

Explicație

Pentru primul test case soluțiile sunt: $(1,1)$, $(1,2)$, $(2,1)$, $(2,2)$.

Pentru cel de-al doilea test case există doar o soluție și anume $(1,1,1)$.