[Solution] Digit Multiplication By K solution codechef

Digit Multiplication By K solution codechef – There is a strange game played in ChefLand.

The game starts with NN white balls, the ii-th of which has a power of SiSi. It is known that 0Si90≤Si≤9. On each level, a black ball with power KK hits each of the white balls. After the collision, the power of each white ball is multiplied by KK.

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

• If K=2K=2, its resulting power is 88 and it remains a single ball.
• If K=13K=13, its resulting power is 5252, so it splits into two white balls with power 55 and 22 respectively.
• If K=27K=27, its resulting power is 108108, so it splits into three white balls with power 1100, and 88 respectively.

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

Please help Chef win the game. Since the answer can be large, print it modulo 109+7109+7.

Input Format

• The first line of input contains a single integer TT, denoting the number of test cases. The description of TT test cases follows.
• The first line of each test case contains three space-separated integers NNKK, and MM.
• The second line of each test case contains a string SS of length NN, where SiSi is the initial power of ii-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+7109+7.

Constraints

• 1T1001≤T≤100
• 1N10001≤N≤1000
• 0K,M1090≤K,M≤109

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 11:

• Initially S=5418S=5418
• After the 1st1st, level S=4536972S=4536972
• After the 2nd2nd level, S=36452754816318S=36452754816318

There are 1414 white balls, so the answer is 1414.

Test case 33: After each level, S=0S=0. So, the answer is 11.