이상한 수열

시간 제한2초메모리 제한512 MB

요약

n이 10^18까지 주어질 때, "2"에서 시작하는 look-and-say 수열의 n번째 항의 길이를 7340033으로 나눈 나머지로 구합니다.

난이도: 어려움10점 중 9점
유형: 행렬, 수학, 동적 계획법
정답자: 아직 제출이 없습니다

문제

다음의 잘 알려진 수열 $s$ 는 숫자 문자열로 이루어진다. $s\_0$ 은 "2"이다. 다음 항은 이전 항을 설명해서 만든다. 이전 항을 같은 숫자가 연속으로 이어진 묶음으로 나눈 뒤, 각 묶음마다 묶음의 크기와 묶음을 이루는 숫자를 차례로 적는다. 처음 몇 항은 다음과 같다.

문자열	설명
$s\_0$ = "`2`"	2가 하나

$s\_1$ = "`12`"	1이 하나, 2가 하나
$s\_2$ = "`1112`"	1이 셋, 2가 하나
$s\_3$ = "`3112`"	3이 하나, 1이 둘, 2가 하나
$s\_4$ = "`132112`"	1이 하나, 3이 하나, 2가 하나, 1이 둘, 2가 하나
$s\_5$ = "`1113122112`"	...

$n$ 번째 항의 길이를 $7\,340\,033$ 으로 나눈 나머지를 구하라.

입력

첫 줄에 정수 $n$ ( $0 \le n \le 10^{18}$ )이 주어진다.

출력

$s\_n$ 의 길이를 $7\,340\,033$ 으로 나눈 나머지를 출력한다.

예제2

예제 1
입력
```
0
```
예상 출력
```
1
```
예제 2
입력
```
2
```
예상 출력
```
4
```