以下、\(0^0=1\)とします。

答えを\(f(n,m)\)とします。

このとき、

\[f(n,m)=s\cdot f(n-1,m)-t\cdot f(n-2,m)+u\cdot f(n-3,m)\]

\[f(n,m)=s\cdot f(n,m-1)-t\cdot f(n,m-2)+u\cdot f(n,m-3)\]

また、

\[\begin{pmatrix}f(0,0)&f(0,1)&f(0,2)\\f(1,0)&f(1,1)&f(1,2)\\f(2,0)&f(2,1)&f(2,2)\end{pmatrix}=\begin{pmatrix}0&0&0\\0&0&1\\0&-1&0\end{pmatrix}\]

であるため、

\[\begin{pmatrix}f(n,m)&f(n,m+1)&f(n,m+2)\\f(n+1,m)&f(n+1,m+1)&f(n+1,m+2)\\f(n+2,m)&f(n+2,m+1)&f(n+2,m+2)\end{pmatrix}=\begin{pmatrix}0&1&0\\0&0&1\\u&-t&s\\\end{pmatrix}^n\begin{pmatrix}0&0&0\\0&0&1\\0&-1&0\end{pmatrix}\begin{pmatrix}0&0&u\\1&0&-t\\0&1&s\\\end{pmatrix}^m\]

となります。 よって、行列累乗によって\(O(\log{n}+\log{m})\)で計算できます。