OMC073(D) - 多項式を利用して漸化式を回避する

　頂点の次数が奇数であるものの総数の求め方の別解です．

　 $n=10^9+10$ とおく． $$f(a,b,c,d)=(ab+ac+ad+bc+bd+cd)^n$$ を展開したときに，どの文字についても次数が奇数であるものの項の係数和が求めるべき総数 $S$ であり， $S$ は $(\pm1,\pm1,\pm1,\pm1)$ に対しそれぞれ $abcd\times{f(a,b,c,d)}$ を計算したときの総和を，$16$ で割ったものである．
　よって， $S=\dfrac{1}{16}(2\cdot6^n+6\cdot(-2)^n)$ であり，Fermatの小定理から,
$$S\equiv(2\cdot6^4+6\cdot(-2)^4)\div16\equiv\textbf{168}\pmod{(n-3)}.$$