结束自己的国际足球生涯后，Cristiano Ronaldo 决定成为 Niue 的公民。为此，他必须通过一场关于 Niue 传统与文化的考试。除了最后一道题，他轻松回答了所有问题，因此他需要你的帮助。你能帮助 Ronaldo 成为 Niue 的公民吗？最后一道题如下：

“对于正整数数组 $a_1,a_2,\ldots,a_n$，我们将其本土程度定义为 $\sum_{i=1}^{n}a_i\cdot f_i$，其中 $f_0=1$、$f_1=1$，且对于 $i\ge 2$，有 $f_i=a_{i-1}f_{i-1}+f_{i-2}$。

此外，如果一个数组在字典序上小于将它反转后得到的数组，我们就称其为 Niue 数组。

给定一个整数 $m$，请计算有多少个 Niue 数组的本土程度不超过 $m$。请给出答案对 $998\,244\,353$ 取模的结果。”

输入格式

第一行包含一个整数 $m$（$1\le m\le 10^{10}$）。

输出格式

输出数组的数量对 $998\,244\,353$ 取模的结果。

样例

输入格式 1

6

输出格式 1

1

输入格式 2

7

输出格式 2

2

输入格式 3

13

输出格式 3

8

输入格式 4

42

输出格式 4

114

输入格式 5

67

输出格式 5

305

输入格式 6

6767

输出格式 6

3471737

输入格式 7

676767

输出格式 7

863282261

输入格式 8

67676767

输出格式 8

217404956

输入格式 9

6767676767

输出格式 9

691869515

说明