After ending his international football career, Cristiano Ronaldo decided that he wants to become a citizen of Niue. To do so, he must pass an exam on Niuean traditions and culture. He answered all the questions easily except for the last one, so he needs your help. Can you help Ronaldo become a citizen of Niue? Here is the final question:
“For array $a_1, a_2, \ldots, a_n$ of positive integers we define it’s nativeness as $\sum_{i=1}^{n} a_i \cdot f_i$, where $f_0 = 1$, $f_1 = 1$ and for $i \ge 2$: $f_i = a_{i-1}f_{i-1} + f_{i-2}$.
Also, we will call an array niuean if it is lexicographically smaller than it’s reverse.
You are given an integer $m$. Please calculate how many niuean arrays have nativeness not bigger than $m$. Give your answer modulo $998\,244\,353$.”
Input
The first line contains one integer $m$ ($1 \le m \le 10^{10}$).
Output
Output number of arrays modulo $998\,244\,353$.
Examples
Input 1
6
Output 1
1
Input 2
7
Output 2
2
Input 3
13
Output 3
8
Input 4
42
Output 4
114
Input 5
67
Output 5
305
Input 6
6767
Output 6
3471737
Input 7
676767
Output 7
863282261
Input 8
67676767
Output 8
217404956
Input 9
6767676767
Output 9
691869515
Note
