Ensure that you are logged in and have the required permissions to access the test.
Given a string S (consisting of digits 0−9) and an integer K.
Pseudo Code:
string fun(string S, int K)
If K == 0:
return S
string R = S + rev(S) # rev(S) will return the reverse of the string S
# '+' denotes concatenation
return fun(R, K-1)
Now, let X be the string returned when S is passed to function fun(). That is,
Find the total number of substrings in X whose decimal representations are divisible by 3. Two substrings will be considered different if the starting or ending indices of both the substrings in X are different. As the answer can be very large print it modulo 109+7.
Note: A substring may have leading zeros. Also, the string S may have leading zeros.
Input Format
First line of the input consists of an integer T denoting the number of testcases. Each testcase consists of string S and integer K separated by space.
Constraints
1≤T≤10
0≤K≤109
1≤|S|≤105 (S denotes length of the string S)
S consists of integers [0,9]
For 50% testcases, 1≤|X|≤109
Output Format
For each of the testcases, output an integer denoting the number of substrings in a newline.
S = "12"
X = "1221"
Substrings = ["1", "2", "2", "1", "12", "22", "21", "122", "221", "1221"]
["12", "21", "1221"] are divisible by 3. Hence, answer is 3.