시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 1 1 1 100.000%

문제

Rikka is a professional problem setter. Today, she is going to generate test cases for a problem about Composite Number.

To randomly generate composite numbers, Rikka starts from a non-empty subset $D$ of digits $\{1,2,\dots, 9\}$ and integer $c = 0$, and then generates in turns. In each turn:

  1. Rikka selects a digit $d$ from $D$ uniformly at random, and then changes $c$ to $c \times 10 + d$;
  2. If $c$ has already been a composite integer, Rikka takes $c$ as the result. Otherwise, Rikka returns to Step $1$ and starts a new turn.

The time cost of a generator is crucial. Therefore, Rikka wants you to calculate the expected number of the turns used by the generator to generate a composite number.

A positive integer $n$ is a composite integer if and only if there exists an integer $k \in [2, n - 1]$ satisfying $k$ is a factor of $n$.

입력

The first line contains a $01$-string of length $9$. The $i$-th character is $1$ if and only if digit $i$ is inside $D$.

The input guarantees that $D$ is not empty.

출력

Output a single integer, representing the expected number of turns.

The answer is guaranteed to be a rational number. You are required to output the answer module $998244353$. Formally, if the simplest fraction representation of the answer is $\frac{x}{y}$, you need to output $x \times y^{998244351} \text{ mod } 998244353$.

예제 입력 1

100000000

예제 출력 1

3

예제 입력 2

001100000

예제 출력 2

499122178

힌트

For the first sample, the generator must return $111$ in the third turn.

For the second sample, there are $3$ possibilities:

  • Return $4$ in the first turn, with probability $\frac{1}{2}$;
  • Return $33$ in the second turn, with probability $\frac{1}{4}$;
  • Return $34$ in the second turn, with probability $\frac{1}{4}$.

Therefore, the expected number of turns is $\frac{3}{2}$.