MARIO là một trò chơi rất quen thuộc với các bạn trẻ. Trong trò chơi, muốn kết thúc một cửa chơi, MARIO phải nhảy để kéo một lá cờ từ đỉnh xuống dưới chân cột cờ. Trong phiên bản mới, MARIO đang ở bờ bên trái sông còn cột cờ được đặt tại bờ bên phải sông, trên sông có \(N\) chiếc cọc gỗ để giúp MARIO sang sông. MARIO có thể nhảy di chuyển từ cọc \(i\) bước sang cọc \(i+1\), hoặc nhảy sang cọc \(i+2\) hoặc nhảy sang cọc \(i+3\). Tuy nhiên, người thiết kế trò chơi có làm khó người chơi bằng cách thiết kế một vài chiếc cọc lung lay, vài chiếc cọc khác lại bị mục nát.

• Với một chiếc cọc \(i\) lung lay: MARIO chỉ có thể bước từ cọc \(i-1\) tới cọc \(i\), và từ cọc \(i\) chỉ có thể bước sang cọc \(i+1\) hoặc nhảy sang cọc \(i+2\)
• Với một chiếc cọc bị mục nát: MARIO không thể đứng trên đó vì nó sẽ gãy và MARIO sẽ bị rơi xuống sông.
• MARIO chỉ có thể đi tiến lên phía trước chứ không thể lùi lại khi đi trên cọc để qua sông.

Cu Tý nhà ta đã rất nhiều lần qua được sông, vì cậu là một game thủ siêu hạng. Tuy nhiên, lần này cậu lại nảy sinh ý nghĩ là phải qua sông theo một cách thật độc đáo để cho đám bạn phải thán phục, vì vậy cậu muốn biết có bao nhiêu cách để qua được sông, từ đó mới chọn ra cách độc đáo nhất. Bạn hãy lập trình, trả lời câu hỏi giúp Cu Tý.

Dữ liệu vào

• Dòng \(1\): Chứa số nguyên dương \(N\) \((1 \le N \le 10^4)\)
• Dòng \(2\): Chứa \(N\) số nguyên \(A_1,A_2...A_N\) với \(A_i\) thuộc tập \(0,1,2\). Trong đó:
  • \(A_i=0\): Nếu cọc \(i\) là cọc tốt
  • \(A_i=1\): Nếu cọc \(i\) là cọc lung lay
  • \(A_i=2\): Nếu cọc \(i\) là cọc bị mục

Dữ liệu ra

• Là số lượng cách đi để có thể qua sông. Do số lượng này rất lớn nên chỉ cần in ra kết quả mod \(10^9\).
• Lưu ý: bờ trái và bờ phải có chức năng tương tự như cọc tốt.

Input 1

7
0 0 2 1 0 0 1

Output 1

6

Input 2

7
0 1 2 1 0 0 0

Output 2

0