국제 축구 선수 경력을 마친 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}$이다.
또한 배열이 자신을 뒤집은 배열보다 사전순으로 작으면 그 배열을 니우에 배열이라고 부른다.
정수 $m$이 주어진다. 토착성이 $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
참고
