F - Find 810s

以下のようなdpを考えます。

• 番目まで決めて810810...810 のうち 文字目まで出てくる通り数

毎回 通り遷移先を求めていると になってTLEしてしまいます。
遷移先が制約下では の 通りしかありえないことと、 が で等しいなら へ遷移する個数の分布も等しいことを利用します。
予め が の場合のそれぞれについてこの分布を計算しておくことで、遷移が で出来るようになり、計算量が になって間に合います。