AtCoder Beginner Contest 178 C問題

AtCoderを始めましたが、ABCのA・B問題はほぼ解ける、C問題は運が良ければ解けるというレベルです。
まずはC問題を難なく解けるというの目標に、まずは過去問のC問題までをどんどんやっていってます。

自力では解けなかった問題を、解説を見て、理解した内容の整理とその結果のコードを書いていきたいと思います。

問題

長さ N の整数の列 A_1,A_2,…,A_N であって以下の条件をすべて満たすものはいくつありますか。

・0 < A_i < 9
・A_i=0 なる i が存在する。
・A_i=9 なる i が存在する。

ただし、答えはとても大きくなる可能性があるので、10^9+7 で割った余りを出力してください。

解けなかった原因

総当たりでは、計算量がかかりすぎるがので、それ以外の方法が必要

解説を見て理解した内容

包除原理を適用して計算する

1. 長さNの整列の組み合わせは、10のN乗
2. i=0が存在しない組み合わせは、9のN乗
3. i=9が存在しない組み合わせは、9のN乗
4. i=0とi=9両方が存在しない組み合わせは、8のN乗

10のN乗(1) - 9のN乗(2) - 10のN乗(3) + 8のN乗（4)
で組合せ数が求まる

ACしたコード

N = int(input().strip())

print( (10**N - 9**N - 9**N +8**N) % (10**9+7) )