Strange Sequence

Time limit2sMemory limit512 MB

Summary

Given n up to 10^18, find the length of the n-th term of the look-and-say sequence starting from "2", modulo 7340033.

Level: Hard9 of 10
Topics: Matrix, Math, Dynamic programming
Solved: No attempts yet

Problem

Consider the following well-known sequence $s$ of digit strings. Let $s\_0$ be "2". Each next term is obtained by describing the previous term: split the previous term into consecutive groups of equal digits, and for each group, write the size of the group followed by the digit it consists of. The first few terms are:

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`"	...

Find the length of the $n$ -th term of this sequence modulo $7\,340\,033$ .

Input

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

Output

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

Examples2

Example 1
Input
```
0
```
Expected output
```
1
```
Example 2
Input
```
2
```
Expected output
```
4
```