#P18109. Native Niuean

Native Niuean

Native Niuean

对于一个非空的正整数数组 a1,a2,…,ana_1,a_2,\ldots,a_n,定义

$$f_0=f_1=1,\qquad f_i=a_{i-1}f_{i-1}+f_{i-2}\quad(i\ge2).$$

该数组的 nativeness 定义为

∑i=1naifi.\sum_{i=1}^n a_i f_i.

如果一个数组的字典序严格小于它反转后的数组,就称它为 niuean 数组。

给定整数 mm,求 nativeness 不超过 mm 的 niuean 数组有多少个。数组长度可以是任意正整数,数组中的每个元素也可以是任意正整数。答案对 998244353998244353 取模。

输入格式

输入一个整数 mm,其中 1≤m≤10101\le m\le10^{10}。

输出格式

输出一个整数,表示所求数组数量对 998244353998244353 取模的结果。

样例 1

输入:

6

输出:

1

样例 2

输入:

7

输出:

2

样例 3

输入:

13

输出:

8

样例 4

输入:

42

输出:

114

样例 5

输入:

67

输出:

305

样例 6

输入:

6767

输出:

3471737

样例 7

输入:

676767

输出:

863282261

样例 8

输入:

67676767

输出:

217404956

样例 9

输入:

6767676767

输出:

691869515