시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 0 0 0 0.000%

문제

Consider the following well-known sequence $s$ consisting of strings of digits. Let $s_0 = $"2". Each next term is obtained by describing the previous term: split the previous term into consecutive groups of equal digits, and for each such group, write the size of the group followed by the digit the group consists of. Thus, the first few terms are constructed as follows:

Your task is to find the length of the $n$-th term of this sequence modulo $7\,340\,033$.

String Description
$s_0 = $"2" one 2
$s_1 = $"12" one 1, one 2
$s_2 = $"1112" three 1s, one 2
$s_3 = $"3112" one 3, two 1s, one 2
$s_4 = $"132112" one 1, one 3, one 2, two 1s, one 2
$s_5 = $"1113122112" ...

Your task is to find the length of the $n$-th term of this sequence modulo $7\,340\,033$.

입력

The first line of input contains one integer $n$ ($0 \le n \le 10^{18}$).

출력

Print the length of $s_n$ modulo $7\,340\,033$.

예제 입력 1

0

예제 출력 1

1

예제 입력 2

2

예제 출력 2

4