농부 존에게는 한 줄로 줄서있는 N마리의 소가 있다. 소들은 왼쪽부터 오른쪽으로 1부터 N까지 번호가 매겨진다.

소들은 그들만의 독특한 시위를 하려고 번호판을 들고 있다. i번 소는 번호 A_i가 적힌 번호판을 들고 있다.

소들은 줄의 순서를 흐트러뜨리지 않고 연속된 한개 또는 여러개의 그룹으로 뭉치려한다. 그대신 그룹에 있는 소들의 번호판에 적힌 번호의 합은 음이 아니여야한다. 농부 존은 소들이 뭉칠 경우의 수가 궁금해졌다. 농부 존을 도와 전체 경우의 수를 1,000,000,009 로 나눈 나머지를 구하자.

예를 들어, 만약 N=4 이고 소들이 들고 있는 번호판이 2, 3, -3, 1 일 경우 소들은 다음과 같이 4가지로 뭉칠 수 있다.

• (2 3 -3 1)
• (2 3 -3) (1)
• (2) (3 -3 1)
• (2) (3 -3) (1)

입력

• 첫 줄에 소의 마릿수, 자연수 N이 주어진다. (1 ≤ N ≤ 100,000)
• 그리고 N개의 줄이 주어지는데, i+1번째 줄에 A_i값이 주어진다. (-10,000 ≤ A_i ≤ 10,000)

출력

입출력 예

입력

4
2
3
-3
1

출력

4

출처: USCAO 2011 February Gold
추천: tamaki