Statement
다다스는 모의고사를 풀다가 다음과 같은 문제를 발견했다.
사진 속 문제를 본 다다스는, 위의 조건을 무시하고 다음과 같은 문제를 풀어버렸다.
길이가 인 양의 정수 수열 이 있다. 이 수열은 아래 두 조건을 만족해야 한다.
- 모든 에 대해
즉, 연속한 세 항이 어떤 양의 정수 에 대해
꼴이 되는 위치가 존재하면 안 된다.
다다스는 조건을 만족하는 수열의 개수가 궁금해졌다. 가능한 수열의 개수를 으로 나눈 나머지를 구하여라.
Input
입력은 다음과 같다.
Output
조건을 만족하는 수열 의 개수를 으로 나눈 나머지를 출력한다.
Constraints
- .
- ().
Subtasks
Samples
Sample 1
Input
6
1 2
1 1
1 2
2 2
1 2
1 2
Output
4
이 예제는 서브태스크 5의 조건을 만족한다.
Sample 2
Input
8
1 10
2 20
1 5
4 40
8 80
1 100
16 160
1 1000
Output
959160770
이 예제는 서브태스크 3, 4, 7의 조건을 만족한다.