팀원 배치

팀원들 N (1 <= N <= 100,000) 명이 한 줄로 서 있고, 각 팀원에게는 1..N까지 번호가 부여되어 있습니다. 각 i 번째 팀원은 정수 A_i (-10,000 <= A_i <= 10,000)가 적힌 카드를 들고 있습니다.

팀 리더는 팀원들이 적절히 구성되면 협업이 잘 이루어질 것을 기대하며, 모든 팀원이 정확히 하나의 그룹에 속하고, 각 그룹의 카드 합계가 음수가 아닌 방법으로 팀원들을 하나 이상의 연속된 그룹으로 구성하려고 합니다.

이렇게 팀원들을 그룹화할 수 있는 방법의 수를 1,000,000,009로 나눈 나머지를 계산해주세요.

예를 들어, N = 4이고 팀원들의 싸인이 2, 3, -3, 1이라면, 다음은 팀원들을 배치할 수 있는 유일한 네 가지 방법입니다:

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

이 예시는 배열의 다른 순서를 계산하는 규칙을 보여줍니다.

• 첫 번째 줄 : 하나의 정수 N
• 두 번째 줄부터 N + 1 번째 줄 : i + 1 번째 줄은 하나의 정수를 포함합니다: A_i

• 첫 번째 줄 : 하나의 정수, (배치 방법의 수를 1,000,000,009로 나눈 나머지)