당신에게 자연수로 이루어진 길이가 n인 배열 b가 주어집니다. 초기에는 모든 수들이 "안티 세포" 안에 들어있습니다. 일반적인 세포는 분열을 하지만, 이 안티 세포는 반대로 여러 안티 세포가 모여 합성을 합니다. 당신은 다음과 같은 과정을 통해 인접한 두 안티 세포를 합치거나 또는 그대로 두려고 합니다.

1. i=0로 설정하고, 빈 배열 c를 하나 만듭니다.
2. i가 n이라면 과정을 종료합니다.
3. b[i]를 포함하는 안티 세포를 X, 그리고 X 바로 왼쪽에 있는 안티 세포를 Y라고 정의합니다. 만약 Y가 존재하고 X의 모든 숫자의 합과 Y의 모든 숫자의 합이 같다면, 당신은 이 두 안티 세포를 합치거나 합치지 않는 행동 중에서 하나를 선택할 수 있습니다.
   1. 만약 X와 Y를 합친다면, 둘을 합치고, c의 맨 뒤에 i를 추가한 뒤 다시 3번 과정으로 돌아갑니다.
   2. 만약 X와 Y를 합치지 않는다면(또는 Y가 존재하지 않는다면), i를 1 증가시키고 2번 과정으로 돌아갑니다.

예를 들어, 다음은 b = [1,1,1,1]일 때 위와 같은 과정을 거치는 것을 나타낸 것입니다.

이 경우 c = [1,3]이 됩니다. 물론 이는 c를 만들 수 있는 하나의 경우일 뿐이며, 당신의 선택에 따라 [], [1], [3], [1,3], [2], [1,3,3]으로 c배열을 다양하게 만들 수 있습니다. 당신이 어떤 선택을 하더라도 유한한 횟수 안에 c 배열을 만들 수 있음은 증명될 수 있습니다.

당신은 b가 주어졌을 때 만들 수 있는 서로 다른 배열 c의 개수가 몇 개인지 알고 싶습니다.

정수로 이루어진 배열 a와 s가 매개변수로 주어집니다. a는 여러 개의 b 배열을 순서대로 이어 붙인 배열이며, s는 각 b 배열의 길이가 순서대로 담긴 배열입니다. 각 b 배열에 대해 문제의 답을 10⁹ + 7로 나눈 나머지를 구하여 배열에 차례대로 담아 return 하도록 solution 함수를 완성해주세요.

예를 들어, a = [1,2,3,4,5,6,7,8,9], s = [2,3,4] 라면, 다음 3가지 b 배열에 대해서 답을 구해야 합니다.

• b = [1,2] (s[0] = 2 이므로, a의 첫 2개 원소가 b 배열을 이룹니다.)
• b = [3,4,5] (s[1] = 3 이므로, a의 그다음 3개 원소가 b 배열을 이룹니다.)
• b = [6,7,8,9] (s[2] = 4 이므로, a의 그다음 4개 원소가 b 배열을 이룹니다.)

제한사항

• 1 ≤ a의 길이 ≤ 200,000
  • 1 ≤ a의 모든 수 ≤ 10⁹
• 1 ≤ s의 길이 ≤ a의 길이
  • 1 ≤ s의 모든 수 ≤ a의 길이
  • s의 모든 수의 합 = a의 길이

입출력 예

입출력 예 설명

입출력 예 #1

• 다음 5개의 b 배열에 대한 답을 구해야 합니다.

• 따라서, [6,3,1,5,9]를 return 해야 합니다.