simulareroalgoedu3 | P4(😐🤣☠️)

This was the problem page during the contest. Access the current page here.
Time limit: 1.5s Memory limit: 256MB Input: Output:

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

Cerință

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

Date de intrare

Pe prima linie veți citi tt, numărul de test cases. Pe următoarele tt linii se vor afla 2 numere, nn și mm.

Date de ieșire

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

Restricții și precizări

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

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,1), (1,2)(1,2), (2,1)(2,1), (2,2)(2,2).

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

Log in or sign up to be able to send submissions!