Ta cần:

$A\left[\begin{array}{ccc}u_n\\u_{n+1}\\u_{n+2}\end{array}\right] = $ $\left[\begin{array}{ccc}u_{n+1}\\u_{n+2}\\u_{n+3}\end{array}\right]$

Từ định nghĩa

`{(u_1=84),(u_2=496),(u_3=3144),(u_(n+3)=13u_(n+2)-50u_(n+1)+56u_n \ (n in NN^**)):}`

Ta suy ra được 

$A=\left[\begin{array}{ccc}0&1&0\\0&0&1\\56&-50&13\end{array}\right]$ 

Triển khai hàm tính lũy thừa nhanh, ta có thể dễ dàng tính `u_{n}` trong O(TlogN) với T là thời gian tính `AB`.

$\\$

$\color{#23d78c}{\texttt{P}}\color{#9ee36f}{\texttt{y}}\color{#10c1ed}{\texttt{t}}\color{#10c1ed}{\texttt{h}}\color{#c6ea64}{\texttt{o}}\color{#fbfb45}{\texttt{n}}$

MOD = 10**9+7
def mod(x):
    return (x + MOD) % MOD
def nhan(a, b):
    m = len(a)
    n = len(a[0])
    p = len(b[0])
    c = [[0]*p for _ in range(m)]
    for i in range(m):
        for j in range(p):
            for k in range(n):
                c[i][j] = mod(c[i][j] + a[i][k] * b[k][j])
    return c
def power(a, n):
    res = a
    n -= 1
    while n > 0:
        if (n & 1): res = nhan(res, a)
        a = nhan(a, a)
        n >>= 1
    return res
a = [[0, 1, 0], [0, 0, 1], [56, -50, 13]]
b = [[84], [496], [3144]]

n = int(input())
if n == 1:
    print(84)
elif n == 2:
    print(496)
elif n == 3:
    print(3144)
else:
    print(nhan(power(a, n-1), b)[0][0])
    
# Author : Daoanhviet96
# Language : Python3

$\\$
\begin{array}{c|c|c}\color{#ffd710}{\texttt{\{}} \color{#8655d6}{\texttt{\{}}\ \ \color{#8cdcda}{\text{Daoanhviet96}}\ \ \color{#8655d6}{\texttt{\}}} \color{#ffd710}{\texttt{\}}}\end{array}