 # TAPSY - EDITORIAL

DIFFICULTY: Medium-Hard
PREREQUISITES: Dynamic-Programming, Matrix-Exponentiation
EXPLANATION:
Let say we have to find the answer to the Query “4”.
1. if we append 1 and 4 at the end of all number having digit’s sum equals 3 then we get digit’s sum as 4.
2. if we append 2 at the end of all number having digit’s sum equals 2 then we get digit’s sum as 4.
3. if we append 3 at the end of all number having digit’s sum equals 1 then we get digit’s sum as 4.

So dp[n]=2*dp[n-1] + dp[n-2] + dp[n-3]

We can solve this by using Matrix Exponentiation

```| F(4) |  =  | 2 1 1 |  *           | F(3) |
| F(3) |     | 1 0 0 |              | F(2) |
| F(2) |     | 0 1 0 |              | F(1) |
```

Similarily for n,

```| F(n)   |  =  | a b c | * | a b c | * ... * | a b c | * | F(3) |
| F(n-1) |     | 1 0 0 |   | 1 0 0 |         | 1 0 0 |   | F(2) |
| F(n-2) |     | 0 1 0 |   | 0 1 0 |         | 0 1 0 |   | F(1) |

| F(n)   |  =  [ | a b c | ] ^ (n-3)   *  | F(3) |
| F(n-1) |     [ | 1 0 0 | ]              | F(2) |
| F(n-2) |     [ | 0 1 0 | ]              | F(1) |
```

Where a,b,c are 2,1,1 respectively.
We can perform (mat)^n for any matrix in Log(n) times.

SOLUTION:
(Python 3)

```mat=[[2,1,1],[1,0,0],[0,1,0]]
val=[13,5,2]
mod=10**9 + 7

def matmul(a,b):
row=len(a)
try:
col=len(b)
except:
col=1
dp=[[0 for i in range(col) ] for j in range(row)]
for i in range(row):
for j in range(col):
ans=0
for k in range(len(b)):
ans+=a[i][k]*b[k][j]
ans%=mod
dp[i][j]=ans
return dp

def solve(mat1,m):
ans=[[1,0,0],[0,1,0],[0,0,1]]

while m>0:
if m%2==1:
ans=matmul(ans,mat1)
m//=2
mat1=matmul(mat1,mat1)
return (ans*val + ans*val + ans*val)%mod

import random as r
t=int(input())
for i in range(t):
n=int(input())
if n<=3:
ans=val[-n]
else:
ans=solve(mat,n-3)
print(ans)
```