first come up solution:

```
f: rewardable
LL: f end with LL
L: f end with L
A: f contain with A
ALL: f contain with A and end with LL
AL: f contain with A and end with L
f[i] = f[i-1] + f[i-1]-LL[i-1]+f[i-1]-A[i-1] # end with P, L, A
A[i] = A[i-1] + A[i-1]-ALL[i-1]+f[i-1]-A[i-1] # end with P, L, A
LL[i] = L[i-1] - LL[i-1] # end with L
L[i] = f[i-1] - LL[i-1] # end with L
ALL[i] = AL[i-1] - ALL[i-1] # end with L
AL[i] = A[i-1] - ALL[i-1] # end with L
```

get TLE, but i didn't realize that can solve by exp. of square, i try to reduce the parameter.

and get `LL[i] = f[i-2] - LL[i-2] - LL[i-1]`

, `ALL[i] = A[i-2] - ALL[i-2] - ALL[i-1]`

and the f & A function, remove the AL and L, still get TLE. I decided continue do, get `f[i] = (f[i-1]*3 - f[i-4]*2 + A[i-4] - A[i-1]), A[i] = (A[i-1]-f[i-4]+f[i-1])`

, doesn't work. finally i remove the function A, get the pure f funcion`f[i] = f[i-1]*3-f[i-2]-f[i-3]-f[i-4]*3+f[i-5]+f[i-6]+f[i-7]`

, finally pass. but it's O(n) time.

```
f = [1, 3, 8, 19, 43, 94, 200, 418]
if n < 8:
return f[n]
for _ in range(7, n):
f[:7] = f[1:]
f[7] = (3*f[6]-f[5]-f[4]-3*f[3]+f[2]+f[1]+f[0]) % 1000000007
return f[7]
```

In fact, every time, we just calculate the map.

0 1 0 0 0 0 0 0

0 0 1 0 0 0 0 0

0 0 0 1 0 0 0 0

0 0 0 0 1 0 0 0

0 0 0 0 0 1 0 0

0 0 0 0 0 0 1 0

0 0 0 0 0 0 0 1

0 1 1 1 -3 -1 -1 3

used exponentiating by squaring , the time is O(log(n))

```
def matrix_multi(a, b):
m, s, n = len(a), len(a[0]), len(b[0])
if len(b) != s:
return
rmtr = [[0]*m for _ in range(n)]
for i in range(m):
for j in range(n):
rmtr[i][j] = sum(a[i][k]*b[k][j] for k in range(s)) % 1000000007
return rmtr
f = [1, 3, 8, 19, 43, 94, 200, 418]
if n < 8:
return f[n]
t = n-7
p = [[0]*8 for _ in range(8)]
for i in range(8):
p[i][i] = 1
mtx = [[0]*8 for _ in range(8)]
for i in range(7):
mtx[i][i+1] = 1
mtx[7] = [0, 1, 1, 1, -3, -1, -1, 3]
while t:
if t & 1:
p = matrix_multi(p, mtx)
mtx = matrix_multi(mtx, mtx)
t >>= 1
return sum(x*y for x,y in zip(p[7], f)) % 1000000007
```

Actually, i should used in the begining.

`[f[i], A[i], LL[i], L[i], ALL[i], AL[i]] = map([f[i-1], A[i-1], LL[i-1], L[i-1], ALL[i-1], AL[i-1]]`

```
def matrix_multi(a, b):
m, s, n = len(a), len(a[0]), len(b[0])
if len(b) != s:
return
rmtr = [[0]*m for _ in range(n)]
for i in range(m):
for j in range(n):
rmtr[i][j] = sum(a[i][k]*b[k][j] for k in range(s)) % 1000000007
return rmtr
p = [[0]*6 for _ in range(6)]
for i in range(6):
p[i][i] = 1
mtx = [\
[3, -1, -1, 0, 0, 0],
[1, 1, 0, 0, -1, 0],
[0, 0, -1, 1, 0, 0],
[1, 0 , -1, 0, 0, 0],
[0, 0, 0, 0, -1, 1],
[0, 1, 0, 0, -1, 0]]
while n:
if n & 1:
p = matrix_multi(p, mtx)
mtx = matrix_multi(mtx, mtx)
n >>= 1
return p[0][0]
```

other matrix also can be generated by the A | L, like the top votes solution.