Fibonacci concatenation solution codechef

Fibonacci concatenation solution codechef

Let’s define Fibonacci concatenation sequence as follows:

  • f[0]=0f[0]=0f[1]=1f[1]=1

  • f[i]=f[i1]+f[i2]f[i]=f[i−1]+f[i−2], for every i2i≥2

Here f[i]f[i] denotes the ithith Fibonacci concatenation number and ++ represents concatenation.

For example, f[2]=f[1]+f[0]=1+0=10f[2]=f[1]+f[0]=1+0=10f[3]=f[2]+f[1]=f[3]=f[2]+f[1]= 10+1=10+1= 101101.

Given an integer nn, you have to determine the sum of digits of all subsequences of the nthnth Fibonacci concatenation number f[n]f[n], modulo 109+7109+7. Fibonacci concatenation solution codechef

subsequence of a number is a sequence of digits that can be derived from the number by deletion of several (possibly, zero or all) digits without changing the order of the remaining digits. The subsequence may even start with trailing zeros. For example 10100101 are subsequences of 101101 while 110110 is NOT a subsequence of 101101. Note that there are 88 subsequences of 101101. The subsequence 11 appears twice and should be counted as different while computing the sum.

Input Format

  • The first line of the input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
  • The first and only line of each test case contains a single integer nn.

Output Format

For each test case, print a single line containing one integer – the sum of digits of all subsequences of f[n]f[n], modulo 109+7109+7.

Constraints

  • 1T1051≤T≤105
  • 1n1051≤n≤105

Sample Input 1  Fibonacci concatenation solution codechef 

3
1
2
3

Sample Output 1 

1
2
8

Explanation Fibonacci concatenation solution codechef

Test case 11: Since f[1]=1f[1]=1, we have only two subsequences, “” (empty subsequence) and “11“. So the sum of digits of both subsequences is 0+1=10+1=1.

Test case 22: Since f[2]=10f[2]=10, we have four subsequences, “” (empty subsequence), “11“, “00” and “1010“. So the sum of digits of all the subsequences is 0+1+0+1=20+1+0+1=2.

Leave a Comment