#P18172. An Easy Counting Problem

An Easy Counting Problem

An Easy Counting Problem

给定整数 k,p,xk,p,x,求满足以下条件的整数数对 (a,b)(a,b) 的数量:

0≤b≤a<pk,(ab)≡x(modp).0\le b\le a<p^k,\qquad\binom ab\equiv x\pmod p.

输出数量对 998244353998244353 取模的结果。

输入格式

一行三个整数 k,p,xk,p,x。其中 kk 以二进制表示给出,从最高位开始,第一位保证为 1;p,xp,x 以通常的十进制给出。

满足

$$1\le k\le2^{1000},\qquad2\le p\le5000,\qquad1\le x<p.$$

保证 pp 是素数。k=21000k=2^{1000} 时,其二进制表示为 1 后跟 1000 个 0,共 1001 位。

注意:条件中的 pkp^k 是 pp 的 kk 次方;kk 的输入形式是二进制,不是十进制字符串。模组合数时使用 pp,最终计数使用另一个模数 998244353998244353。

输出格式

输出一个整数,表示满足条件的数对数量模 998244353998244353 的结果。

样例 1

输入:

1 7 5

输出:

2

样例 2

输入:

1 43 17

输出:

17

样例 3

输入:

1111111111 4999 1954

输出:

195378837