3つの整数 $k, p, x$ が与えられます。以下の条件を満たす整数の組 $(a, b)$ の個数を求めてください。
- $0 \le b \le a < p^k$
- $\binom{a}{b} \equiv x \pmod{p}$
入力
入力は1行のみで、3つの整数 $k$ ($1 \le k \le 2^{1000}$)、$p$ ($2 \le p \le 5000$)、$x$ ($1 \le x < p$) が含まれます。 整数 $k$ は、最上位ビットから始まる二進数表記で与えられます。 $p$ は素数であり、$k$ の入力の最初の桁は $1$ であることが保証されています。
出力
答えを $998244353$ で割った余りを1つの整数として出力してください。
入出力例
入出力例 1
1 7 5
2
入出力例 2
1 43 17
17
入出力例 3
1111111111 4999 1954
195378837