#49 모의고사 문제

문제

다다스는 모의고사를 풀다가 다음과 같은 문제를 발견했다. 화면 캡처 2026-05-10 011119.png

사진 속 문제를 본 다다스는, 위의 조건을 무시하고 다음과 같은 문제를 풀어버렸다.

길이가 $N$ 인 양의 정수 수열 $A_1, A_2, \ldots, A_N$ 이 있다. 이 수열은 아래 두 조건을 만족해야 한다.

A_i = A_{i+1}, \quad A_i + A_{i+1} = A_{i+2}

즉, 연속한 세 항이 어떤 양의 정수 $x$ 에 대해

x,\ x,\ 2x

꼴이 되는 위치가 존재하면 안 된다.

다다스는 조건을 만족하는 수열의 개수가 궁금해졌다. 가능한 수열의 개수를 $10^9+7$ 으로 나눈 나머지를 구하여라.

입력은 다음과 같다.

$N$ $L_1 \ R_1$ $L_2 \ R_2$

조건을 만족하는 수열 $A$ 의 개수를 $10^9 + 7$ 으로 나눈 나머지를 출력한다.

#	점수	제한
1	1	$N \leq 2$ .
2	15	$N \leq 10$ . $R_i \leq 10$ ().

예제 1

입력

출력

4

이 예제는 서브태스크 5의 조건을 만족한다.

예제 2

입력

출력

959160770

이 예제는 서브태스크 3, 4, 7의 조건을 만족한다.