004 - FizzBuzz Subsequence Problem

問題

自然数$N$(1≤$N$≤10¹⁰⁵)がある。
$N$から1つ以上の任意の桁を抽出し、順序を変えずに結合した値を部分列数と仮称する。
たとえば、$N$=334のとき、部分列数は(3, 3, 4, 33, 34, 34, 334)がある。
また、15で割り切れる数を特別にFizzBuzz数と仮称する。
$N$が与えられるので、部分列数がFizzBuzz数である場合はいくつあるか求めよ。
2つの部分列数が同じであっても、取り出す位置が異なれば区別する。
なお、答えは非常に大きくなる場合があるため998244353で割ったあまりを出力する。

入出力例

例1

入力

45

出力

1

部分列数としては(4, 5, 45)の三つがあるが、FizzBuzz数なのは45のみ。

例2

入力

300

出力

6

300の部分列数は(3, 0, 0, 30, 30, 00, 300)があるが、このうち(0, 0, 30, 30, 00, 300)がFizzBuzz数にあたるので、6を出力。 00も任意の桁を抽出することでできるので、部分列数として成り立つ。

例3

入力

300000000000000000000000000000

出力

75497469