문제

대회를 준비하느라 고생한 짐비를 위해 수열을 선물해주기로 했다. 짐비가 선물로 받기에 적절한 수열을 생각하다가 짐비의 아이디인 gmb9817에서 을 숫자별로 끊어 나열한 수열인 은 , 과 같이 앞의 두 항의 뺄셈 결과가 다음 항이 되는 규칙을 발견하고, 이를 바탕으로 gmb 수열을 만들게 되었다.

gmb 수열의 정의는 아래와 같다.

• 길이가 이상인 수열 가 gmb 수열이라는 것은 를 만족하는 모든 정수 에 대해 라는 것을 뜻한다.
• 길이가 이하인 모든 수열은 gmb 수열이 아니다. 따라서 빈 수열도 gmb 수열이 아니다.

하지만 아무 수열이나 선물하면 짐비가 만족하지 않을 수 있기 때문에, 해당 수열을 선물받았을 때 그의 만족도를 알아볼 필요가 있다.

수열 에 대해 만족도는 아래와 같이 정의한다.

• 수열 의 모든 개의 부분 수열 중 gmb 수열인 것의 개수

어떠한 수열 가 주어졌을 때 해당 수열의 만족도를 구해주도록 하자.

입력

첫 번째 줄에 수열 의 길이 이 주어진다.

두 번째 줄에 음이 아닌 정수 이 공백으로 구분되어 주어진다.

출력

첫 번째 줄에 수열 의 만족도를 로 나눈 나머지를 출력한다.

노트

길이가 인 수열 가 주어졌을 때, 의 부분 수열(subsequence)는 다음과 같이 정의한다.

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