Digit Multiplication By K solution codechef – There is a strange game played in ChefLand.
The game starts withwhite balls, the -th of which has a power of . It is known that . On each level, a black ball with power hits each of the white balls. After the collision, the power of each white ball is multiplied by .
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.
- If , its resulting power is and it remains a single ball.
- If , its resulting power is , so it splits into two white balls with power and respectively.
- If , its resulting power is , so it splits into three white balls with power , , and respectively.
The aim of the game is to determine the number of white balls afterlevels. Note that remains the same for every level.
Please help Chef win the game. Since the answer can be large, print it modulo.
- The first line of input contains a single integer , denoting the number of test cases. The description of test cases follows.
- The first line of each test case contains three space-separated integers , , and .
- The second line of each test case contains a string of length , where is the initial power of -th ball.
For each test case, output in a single line the number of white balls at the end of the game, modulo.
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
- After the , level
- After the level,
There arewhite balls, so the answer is .
Test case: After each level, . So, the answer is .