Eddy likes to play with digits. However, as you may know, Eddy is a programmer not a normal human. Thus, he likes to play with hexadecimal digits instead of decimal digits. One day, he found that sum of digits is very interesting. Then, he invents following function. funcSOD:texttt{func SOD:}funcSOD: ifv
Eddy likes to play with digits. However, as you may know, Eddy is a programmer not a normal human. Thus, he likes to play with hexadecimal digits(base 16) instead of decimal digits(base 10). One day, he found that sum of digits(SODtexttt{SOD}SOD) is very interesting. Then, he invents following function. func SOD(v):texttt{func SOD(v):}func SOD(v): if v<16: return vtexttt{ if v<16: return v} if v<16: return v return SOD(sum of digits of v in hexadecimal)texttt{ return SOD(sum of digits of v in hexadecimal)} return SOD(sum of digits of v in hexadecimal) After playing with SODtexttt{SOD}SOD several times, Eddy found that for one integer, the computation is too easy to make him happy. Thus, Eddy generates a string of hexadecimal digits S, and takes some subsegment(consecutive digits) of it. Then, Eddy takes all the non-empty subsequence(not necessary consecutive digits) from the subsegment as the inputs of the SODtexttt{SOD}SOD function. It becomes a little challenging for Eddy now. But, Eddy is still not satisfied. He wants to change the string sometimes and keeps taking some subsegments as queries. Now, it's really a problem for Eddy. You, as one of the friends of Eddy, come to rescue him and are going to compute the answer for him. Since the number of outputs would be too many(which will be equal to the number of non-empty subsequences), you are only required to compute the number of each output and report the number (∑(number of outputs being i)×1021i)mod 109+7(1000000007)(sum (text{number of outputs being }i) times 1021^i) mod 10^9+7(1000000007)(∑(number of outputs being i)×1021i)mod109+7(1000000007) to Eddy. For example, the hexadecimal string S equals 12345texttt{12345}12345. Eddy takes the subsegment [1,1] which is 1texttt{1}1. All the non-empty subsequence is [1][texttt{1}][1]. Thus, the answer will be ∑1×10211mod 109+7=1021sum 1 times 1021^1 mod 10^9+7 = 1021∑1×10211mod109+7=1021. If Eddy takes the subsegment [1,3] which is 123texttt{123}123. All the non-empty subsequence is [1,2,3,12,13,23,123][texttt{1}, texttt{2}, texttt{3}, texttt{12}, texttt{13}, texttt{23}, texttt{123}][1,2,3,12,13,23,123]. Then, the answer will be 267411465.
