以下、\(0^0=1\)とします。 答えを\(f(n,m)\)とします。

このとき、\(x,y\)について以下の形式的べき級数を考えます。

\[\sum_{n=0}^{\infty}\sum_{m=0}^{\infty}f(n,m)x^ny^m\]

ここで、

\[\sum_{n=0}^{\infty}\sum_{m=0}^{\infty}a^nb^mx^ny^m=\dfrac{1}{1-ax}\cdot \dfrac{1}{1-by}\]

であることに注意すると、

\[\sum_{n=0}^{\infty}\sum_{m=0}^{\infty}f(n,m)x^ny^m=\dfrac{xy^2-yx^2}{(1-\alpha x)(1-\beta x)(1-\gamma x)(1-\alpha y)(1-\beta y) (1-\gamma y)}\]

となります。 また、

\[(1-\alpha x)(1-\beta x)(1-\gamma x)=1-(\alpha+\beta +\gamma)x+(\alpha \beta+\beta\gamma+\gamma\alpha)x^2-\alpha\beta\gamma x^3=1-sx+tx^2-ux^3\]

であるため、

\([x^n]f(x)\)を\(f(x)\)の\(x^n\)の係数とすると、

\[f(n,m)=\left([x^n]\dfrac{x}{1-sx+tx^2-ux^3}\right)\left([y^m]\dfrac{y^2}{1-sy+ty^2-uy^3}\right)-\left([x^n]\dfrac{x^2}{1-sx+tx^2-ux^3}\right)\left([y^m]\dfrac{y}{1-sy+ty^2-uy^3}\right)\]

となります。それぞれの級数の値についてはBostan-Mori algorithmなどを使うと\(O(\log{n}+\log{m})\)で計算できます。