Rikka 是一位专业的题目出题人。今天，她要为一道关于合数的题目生成测试数据。

为了随机生成合数，Rikka 从数字 $\{1, 2, \dots, 9\}$ 的一个非空子集 $D$ 和整数 $c = 0$ 开始，然后轮流生成。在每一轮中：

1. Rikka 从 $D$ 中等概率随机选择一个数字 $d$，然后将 $c$ 更新为 $c \times 10 + d$；
2. 如果 $c$ 已经是一个合数，Rikka 将 $c$ 作为结果。否则，Rikka 回到第 1 步并开始新的一轮。

生成器的耗时至关重要。因此，Rikka 希望你计算生成器生成一个合数所使用的期望轮数。

一个正整数 $n$ 是合数，当且仅当存在一个整数 $k \in [2, n - 1]$ 满足 $k$ 是 $n$ 的因数。

输入格式

第一行包含一个长度为 9 的 01 字符串。如果第 $i$ 个字符为 1，则表示数字 $i$ 在集合 $D$ 中。 输入保证 $D$ 非空。

输出格式

输出一个整数，表示期望轮数。 答案保证是一个有理数。你需要输出答案对 $998244353$ 取模的结果。形式化地，如果答案的最简分数表示为 $\frac{x}{y}$，你需要输出 $x \times y^{998244351} \pmod{998244353}$。

样例

输入格式 1

100000000

输出格式 1

3

说明

对于第一个样例，生成器必须在第三轮返回 111。

输入格式 2

001100000

输出格式 2

499122178

说明

对于第二个样例，有 3 种可能性：

• 第一轮返回 3，概率为 $\frac{1}{2}$；
• 第二轮返回 43，概率为 $\frac{1}{4}$；
• 第二轮返回 44，概率为 $\frac{1}{4}$。

因此，期望轮数为 $1 \times \frac{1}{2} + 2 \times (\frac{1}{4} + \frac{1}{4}) = \frac{3}{2}$。