23862번 - Digidivisible Numbers 서브태스크다국어

문제

Let's call a number digidivisible in base $B,ドル if it is divisible by all digits in its base $B$ representation. For example, 728ドル_{10}$ is divisible by 7ドル,ドル 2ドル$ and 8ドル,ドル so it is digidivisible in base 10ドル,ドル and number 264ドル_8 = 180_{10}$ is divisible by 2ドル,ドル 6ドル$ and 4ドル,ドル so it is digidivisible in base 8ドル$.

You are given integers $B$ and $n,ドル and some set of allowed digits from 1ドル$ to $B-1$. Find the number of digidivisible numbers consisting of $n$ digits in base $B,ドル only containing these allowed digits. Solve this problem for some fixed $n$ and $B$ and for multiple sets of allowed digits.

입력

The first line contains two integers $B$ and $n$ (2ドル \le B \le 10$; 1ドル \le n \le 10^9$). The second line contains an integer $t$ (1ドル \le t \le 2^{B-1} - 1$) --- the number of sets of allowed digits you need to solve this problem for.

Then, $t$ lines follow, $i$-th line contains a single string $s_i,ドル consisting of $B$ zeros and ones. If $s_{i,k} = 1$ (indices begin with 0), then digit $k$ is allowed, otherwise digit $k$ is forbidden. Each set has at least one allowed digit, and digit 0ドル$ is always forbidden. All $t$ sets are distinct.

출력

For each one of the $t$ sets print the answer in a separate line. Because the result might be huge, print it modulo 999ドル\;999\;001$.

제한

서브태스크

힌트

Total number of 3-digit digidivisible numbers in base 10 is 56ドル$. If we only allow even digits, then there are 17 numbers left: 222, 224, 244, 248, 264, 288, 424, 444, 448, 488, 624, 648, 666, 824, 848, 864, 888.