Chú ếch Bin phải qua một con sông để về nhà. Từ bờ trái đến bờ phải có \(N\) hòn đá xếp thành một hàng, đánh số \(1, 2, \dots, N\) theo chiều từ trái sang phải. Ta coi bờ trái là vị trí \(0\) và bờ phải là vị trí \(N+1\). Bin xuất phát ở bờ trái và chỉ được nhảy về phía bờ phải: từ vị trí \(x\) có thể nhảy tới \(x+1\), \(x+2\) hoặc \(x+3\) (không được vượt quá bờ phải, cũng không được nhảy lùi).
Mỗi hòn đá thuộc một trong ba loại:
- Loại \(0\) (đá chắc): không có hạn chế gì.
- Loại \(1\) (đá lung lay): Bin chỉ có thể đáp xuống nó bằng bước nhảy \(+1\) (tức là từ vị trí ngay trước nó), và khi đứng trên nó chỉ có thể nhảy \(+1\) hoặc \(+2\) (không được nhảy \(+3\)).
- Loại \(2\) (đá mục): Bin không được đáp xuống hòn đá này.
Hai bờ sông được coi như đá chắc.
Hãy đếm số cách khác nhau để Bin đi từ bờ trái sang bờ phải (hai cách khác nhau nếu tập các vị trí đã đặt chân khác nhau). Vì kết quả có thể rất lớn nên chỉ cần in ra phần dư khi chia cho \(10^9\) (không cần thêm số 0 ở đầu).
- Dòng đầu tiên chứa số nguyên dương \(N\).
- Dòng thứ hai chứa \(N\) số nguyên \(A_1, A_2, \dots, A_N\) với \(A_i \in \{0, 1, 2\}\) là loại của hòn đá thứ \(i\).
Output
In ra một số nguyên là số cách qua sông, lấy phần dư khi chia cho \(10^9\).
Constraints
- \(1 \le N \le 10000\)
- \(A_i \in \{0, 1, 2\}\)
Sample Output 1
Sample Output 2
Explanation
Ở ví dụ 2, hòn đá thứ 4 bị mục nên không thể đặt chân. Để vượt qua nó phải nhảy từ vị trí 3 sang vị trí 5, nhưng hòn đá 5 lung lay và chỉ có thể đáp xuống từ vị trí 4, nên không có cách nào qua sông.
