给定三个整数 $k, p, x$。求满足以下条件的整数对 $(a, b)$ 的数量：
- $0 \le b \le a < p^k$；
- $\binom{a}{b} \equiv x \pmod{p}$。
输入格式
输入仅一行，包含三个整数：$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 7 5
样例输出 1
2
样例输入 2
1 43 17
样例输出 2
17
样例输入 3
1111111111 4999 1954
样例输出 3
195378837