#P9615. 牛表

牛表

题目描述

给出三个整数 x,y,P(1≤x,y<P)x,y,P(1 \le x, y < P),PP 为素数,可以重复对 xx 执行如下操作:

  • 选择一个整数 z∈[1,P−1]z\in[1,P-1],花费 ∣x−z∣|x-z| 的牛币,使得 x=x×z mod Px=x\times z\bmod P。

最小需要花费多少牛币才能使得 x=yx=y?

设 ans(i,j)ans(i,j) 为当 x=i,y=jx = i, y = j 时的答案,为了减少输出,你需要输出 $\displaystyle \sum^{P-1}_{i=1}\sum^{P-1}_{j=1} ans(i,j)t^{(i-1)\times (P-1)+j-1} \bmod 998244353$。

输入格式

输入一行两个整数 P,tP,t。

输出格式

输出一行一个整数表示答案。

样例

2 1
0

ansans 矩阵为:

0

答案为:0×10=00\times 1^0=0。

3 233
233

ansans 矩阵为:

0 1
0 0

答案为:$0\times 233^0+1\times 233^1+0\times 233^2+0\times 233^3=233$。

5 233
889807030

ansans 矩阵为:

0 1 2 1
0 0 2 0
0 1 0 0
0 1 2 0
1999 2333
982345126

数据范围

测试点 数据约束
1∼41\sim 4 P≤50P\le 50
5∼85\sim 8 P≤500P\le 500
9∼129\sim 12 P≤103P\le 10^3
13∼2013\sim 20 无特殊限制

对于全部数据,2≤P≤2×1032\le P\le 2\times 10^3,1≤t≤5×1031\le t\le 5\times 10^3。