Description

已知An =K^n * An-1^m和A0求An mod p

Format

Input

第一行两个数T，p表示数据组数和p

接下来T行每行4个数分别表示MA0 K n

Output

T行，每行一个数表示答案

Samples

1 10000000007
2 2 2 2

256

Limitation

对于100%的数据 T=2500 p<=10^12 n,M,A0,K<=10^18 p与A0互质 p与K互质