34984번 - gmb 수열

대전대신고등학교 선배들은 제1회 코더즈 코딩페어를 준비하느라 고생한 짐비를 위해 수열을 선물해 주기로 했다.

짐비가 선물로 받기에 적절한 수열을 생각하던 선배들은 짐비의 BOJ 핸들인 gmb9817에 주목했다. 핸들 뒷부분의 네 자리 숫자 $9817$을 숫자별로 끊어 나열한 수열인 $[9, 8, 1, 7]$은 $9-8=1$, $8-1=7$과 같이 앞의 두 항의 뺄셈 결과가 다음 항이 되는 규칙이 있었던 것이다.

선배들은 이 규칙을 바탕으로 gmb 수열을 만들게 되었다. gmb 수열의 정의는 아래와 같다.

• 길이가 $3$ 이상인 수열 $[A_1, A_2, \cdots, A_K]$ 중 $1\le x\le K-2$를 만족하는 모든 정수 $x$에 대해 $A_x-A_{x+1}=A_{x+2}$를 만족할 때, ​​​​gmb 수열이라고 한다.
• 길이가 $2$ 이하인 모든 수열은 gmb 수열이 아니다. 따라서 빈 수열도 gmb 수열이 아니다.

하지만 아무 수열이나 선물하면 짐비가 만족하지 않을 수 있기 때문에, 선배들은 짐비가 수열을 선물 받았을 때 얼마나 만족할지를 나타내는 척도인 만족도를 알아보기로 했다. 길이 $N$인 수열 $B$에 대해 만족도는 $B$의 $2^N$개의 부분 수열 중 gmb 수열인 것의 개수로 정의된다.

선배들을 위해, 수열 $B$가 주어졌을 때 해당 수열의 만족도를 구해보자.

첫번째 줄에 수열 $B$의 길이 $N$이 주어진다. $(1 \le N \le 2 \times 10^5)$

두번째 줄에 음이 아닌 정수 $B_1, B_2, \cdots, B_N$이 공백으로 구분되어 주어진다. $(0 \le B_i < 300)$

첫번째 줄에 수열 $B$의 만족도를 $10^9+7$로 나눈 나머지를 출력한다.

길이가 $N$인 수열 $B=[B_1, B_2, \cdots, B_N]$가 주어졌을 때, $B$의 부분 수열(subsequence)은 다음과 같이 정의한다.

• $[B_{i_1}, B_{i_2}, \cdots, B_{i_m}]\ \ (1\le i_1<i_2<\cdots<i_m\le N;\ 0\le m\le N)$

이때, 두 부분 수열이 동일한 원소를 같은 순서로 포함하더라도, 인덱스 선택 $(i_1, i_2, \cdots, i_m)$이 서로 다르면 서로 다른 부분 수열로 본다. 즉 부분 수열은 값의 나열뿐 아니라 인덱스 선택의 조합으로 구별된다.