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