시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB0000.000%

문제

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$.

서브태스크

번호배점제한
18

$B = 10$, $n \le 5$, $t = 1$, all digits except $0$ are allowed

29

$B \le 10$, $B^n \le 10^5$, $t = 1$

39

$B \le 10$, $B^n \le 10^5$

432

$B \le 10$, $n \le 50$

513

$B \le 6$, $n \le 10^9$

614

$B \le 8$, $n \le 10^9$

715

$B \le 10$, $n \le 10^9$

예제 입력 1

10 3
2
0111111111
0010101010

예제 출력 1

56
17

힌트

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.

채점 및 기타 정보

  • 예제는 채점하지 않는다.