Rikka with Composite Number

Rikka는 프로 문제 출제자다. 오늘 그녀는 합성수에 관한 문제의 테스트 케이스를 만들려고 한다.

합성수를 무작위로 생성하기 위해, Rikka는 빈 집합이 아닌 숫자 집합 $D \subseteq \{1,2,\dots, 9\}$와 정수 $c = 0$에서 시작하여 다음을 반복한다. 매 턴마다:

1. Rikka는 $D$에서 숫자 $d$를 균등한 확률로 선택한 뒤 $c$를 $c \times 10 + d$로 바꾼다.
2. $c$가 이미 합성수라면, Rikka는 $c$를 결과로 삼는다. 그렇지 않으면 1단계로 돌아가 새 턴을 시작한다.

생성기의 시간 비용은 중요하다. 따라서 Rikka는 생성기가 합성수를 생성하기 위해 사용하는 턴 수의 기댓값을 계산하기를 원한다.

양의 정수 $n$이 합성수라는 것은 $n$의 약수인 정수 $k \in [2, n - 1]$가 존재한다는 것과 동치이다.

첫째 줄에 길이 $9$인 $01$-문자열이 주어진다. $i$번째 문자가 $1$인 것은 숫자 $i$가 $D$에 속한다는 것과 동치이다.

입력에서 $D$는 비어 있지 않음이 보장된다.

턴 수의 기댓값을 나타내는 정수 하나를 출력한다.

답은 유리수임이 보장된다. 답을 $998244353$으로 나눈 나머지를 출력해야 한다. 구체적으로, 답의 기약분수 표현이 $\frac{x}{y}$일 때, $x \times y^{998244351} \text{ mod } 998244353$을 출력한다.

첫 번째 예제에서 생성기는 세 번째 턴에 반드시 $111$을 반환한다.

두 번째 예제에서는 $3$가지 경우가 있다:

• 첫 번째 턴에 $4$를 반환할 확률은 $\frac{1}{2}$이다.
• 두 번째 턴에 $33$을 반환할 확률은 $\frac{1}{4}$이다.
• 두 번째 턴에 $34$를 반환할 확률은 $\frac{1}{4}$이다.

따라서 턴 수의 기댓값은 $\frac{3}{2}$이다.