You are given three integers $k, p, x$. Find the number of integer pairs $(a, b)$ that satisfy the following conditions:

1. $0 \le b \le a < p^k$;
2. $\binom{a}{b} \equiv x \pmod{p}$.

Input

The only line of the input contains three integers: $k$ ($1 \le k \le 2^{1000}$), $p$ ($2 \le p \le 5000$) and $x$ ($1 \le x < p$). The integer $k$ is given in its binary form, starting from the highest bit. It is guaranteed that $p$ is prime and that the first digit of $k$ in the input is 1.

Output

Output a single integer – the answer modulo 998244353.

Examples

Input 1

1 7 5

Output 1

2

Input 2

1 43 17

Output 2

17

Input 3

1111111111 4999 1954

Output 3

195378837