Cerința

Se dau N perechi de numere n k. Pentru fiecare pereche să se calculeze numărul de divizori al lui \(P = {k}^{n} \cdot \left(1 + 2 + 3 + \cdots + k \right) \).

Date de intrare

Fișierul de intrare nr_div_huge.in conține pe prima linie numărul N, iar pe următoarele N linii N perechi de numere n și k separate printr-un spațiu.

Date de ieșire

Fișierul de ieșire nr_div_huge.out va conține pe linia i, 1 ≤ i ≤ N, numărul D, reprezentând numărul de divizori al lui P, calculat pentru perechea cu numărul i. Pentru că acesta poate fi foarte mare se va afișa modulo 1.000.000.007.

Restricții și precizări

• 1 ≤ N ≤ 15.000
• 1 ≤ k, n ≤ 1.000.000.000

Exemplu:

nr_div_huge.in

2
2 3
4 4

nr_div_huge.out

8
20

Explicație

Pentru prima pereche: P=54, iar 54 are 8 divizori.

Pentru cea de-a doua pereche: P=2560, iar 2560 are 20 divizori