Sadə cəmi

Verilmiş üç tam ədəd x, m və n. Aşağıdakı ifadəni hesablayın: (1 + x + x^2 + ... + x^m) (mod n).

Giriş məlumatları

Birinci sətir testlərin sayını göstərir. Sonrakı hər sətir üç tam ədəd x, m və n (1 ≤ x, m, n ≤ 10^16) ehtiva edir.

Çıxış məlumatları

Hər bir test üçün nəticəni ayrı sətirdə verin.

Nümunələr