Fie o matrice (care are M linii si N coloane) colorată folosind C culori. Aceasta este K-frumoasă doar dacă are exact K coloane omogene. O coloană omogenă este o coloană care are toate elementele colorate la fel.

Cerința

Știind T (reprezentând numărul de teste), p, Mi, Ni, Ci și Ki (1 ≤ i ≤ T), să se determine numărul de posibilități modulo p de a colora întreaga matrice (folosind cele Ci culori) pentru a o face K-frumoasă.

Date de intrare

În fișierul fmat.in se vor citi:
Pe prima linie: T și p.
Pe următoarele T linii: Mi, Ni, Ci și Ki.

Date de ieșire

În fișierul fmat.out se vor afișa răspunsurile celor T teste, câte unul pe linie.

Restricții și precizări

• 1 ≤ T ≤ 200.000
• 2 ≤ p ≤ 1.000.000.000 (p - prim)
• 1 ≤ Mi ≤ Ci ≤ Ni ≤ 1.000.000
• 0 ≤ Ki ≤ 500.000
• X modulo p = restul impărțirii lui X la p.
• Pentru 10 puncte, Ki ≤ 2 si Ni ≤ 4.
• Pentru alte 20 de puncte, Ni ≤ 5.000.
• Toate numerele din fișierul de intrare vor fi numere naturale.

Exemplu

fmat.in

4 20113
2 3 3 0
3 3 3 9
2 4 3 1
3 3 3 0

fmat.out

216
0
2592
13824