Ensure that you are logged in and have the required permissions to access the test.

Fun With 3

4.5

2 votes
Combinatorics, Modular arithmetic, Easy-Medium
Problem

Given a string S (consisting of digits 09) 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,

                                         X=fun(S,K)

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

  • 1T10

  • 0K109

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

Time Limit: 2
Memory Limit: 256
Source Limit:
Explanation

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.

Editor Image

?