Masala #0745

Sizga \(N = P_1^{A_1} * P_2^{A_2} * \dots * P_x^{A_x}\)  soni berilgan. Bu yerda \(P\) tub sonlardan tashkil topgan massiv (hech bir elementi takrorlanmaydi), \(A\) natural sonlardan tashkil topgan massiv. Sizning vazifangiz tub ko’paytuvchilari tarkibiga \(N\) sonining tub ko’paytuvchilari tarkibidagi barcha tub sonlar qatnashgan hamda \(N\) sonining bo’luvchisi bo’la oladigan natural sonlar yig’indisini chop eting.

Kirish faylining dastlabki satrida bitta butun son, \(T (1 \le T \le 10)\) testlar soni kiritiladi.

Keyingi qatordan boshlab har bir test uchun birinchi qatorda \(X (1 \le X \le 100000)\) \(N\) sonining tub ko’paytuvchilari tarkibida nechta tub son ishtirok etgani kiritiladi. Ikkinchi satrda bo’sh joy bilan ajratilgan holda \(N\) ta natural son, \(P (0 < P_i < 10^6)\) tub sonlar ro’yxati kiritiladi. Uchinchi satrda bo’sh joy bilan ajratilgan holda \(N\) ta natural son, \(A (1 \le A_i \le 10^9)\) massiv elementlari kiritiladi.

Chiqish faylida har bir test uchun alohida satrda masala javobini \(10^9+7\) ga bo’lgandagi qoldiqni chop eting