F. An Easy Counting Problem
time limit per test
6 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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 \lt 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 \lt 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 7 5
Output
2
Input
1 43 17
Output
17
Input
1111111111 4999 1954
Output
195378837