Code Solution

 

Digit Multiplication By K Problem Code: DIGMULK

Submit

There is a strange game played in ChefLand.

The game starts with N$N$ white balls, the i$i$-th of which has a power of Si$S_i$. It is known that 0≤Si≤9$0\le S_i\le 9$. On each level, a black ball with power K$K$ hits each of the white balls. After the collision, the power of each white ball is multiplied by K$K$.

However, white balls are only allowed to have single-digit power. In order to maintain this, a white ball whose power contains multiple digits splits into several white balls with single-digit power, one per digit.

For example, consider a white ball with a power of 4$4$.

• If K=2$K=2$, its resulting power is 8$8$ and it remains a single ball.
• If K=13$K=13$, its resulting power is 52$52$, so it splits into two white balls with power 5$5$ and 2$2$ respectively.
• If K=27$K=27$, its resulting power is 108$108$, so it splits into three white balls with power 1$1$, 0$0$, and 8$8$ respectively.

The aim of the game is to determine the number of white balls after M$M$ levels. Note that K$K$ remains the same for every level.

Please help Chef win the game. Since the answer can be large, print it modulo 109+7${10}^9+7$.

Input Format

• The first line of input contains a single integer T$T$, denoting the number of test cases. The description of T$T$ test cases follows.
• The first line of each test case contains three space-separated integers N$N$, K$K$, and M$M$.
• The second line of each test case contains a string S$S$ of length N$N$, where Si$S_i$ is the initial power of i$i$-th ball.

Output Format

For each test case, output in a single line the number of white balls at the end of the game, modulo 109+7${10}^9+7$.

Constraints

• 1≤T≤100$1\le T\le 100$
• 1≤N≤1000$1\le N\le 1000$
• 0≤K,M≤109$0\le K,M\le {10}^9$

Subtasks

Subtask #1 (100 points): Original constraints

Sample Input 1 

3
4 9 2
5418
5 63 3
40514
1 100000 100000
0

Sample Output 1 

14
88
1

Explanation

Test case 1$1$:

• Initially S=5418$S=5418$
• After the 1st$1^{st}$, level S=4536972$S=4536972$
• After the 2nd$2^{nd}$ level, S=36452754816318$S=36452754816318$

There are 14$14$ white balls, so the answer is 14$14$.

Test case 3$3$: After each level, S=0$S=0$. So, the answer is 1

Solution:

click here for solution