Cho một dãy n số nguyên A = (a₁, a₂,..., a_n). Ta định nghĩa dãy con của một dãy A cho trước là một dãy thu được bằng cách xóa đi một số phần tử của dãy A, các phần tử còn lại vẫn giữ đúng thứ tự.

Ví dụ: Cho dãy A = (8 6 5 2 7 4 9) với N = 7, dãy (6 5 4 9) là 1 dãy con của A.

Yêu cầu: Hãy cho biết có bao nhiêu dãy con của dãy thỏa mãn các phần tử có giá trị chẵn, lẻ hoặc lẻ, chẵn xen kẽ nhau?

Dữ liệu vào gồm:

- Dòng đầu giá trị của số nguyên dương n (n ≤ 1000).

- Dòng thứ hai chứa n số nguyên a_i, mỗi số cách nhau một khoảng trắng (i = 1,2, ..., n; |a_i| < 10⁶).

Dữ liệu ra: Một số nguyên duy nhất là số lượng dãy con thỏa mãn yêu cầu đề bài sau khi chia lấy dư cho 10⁹ +7. 

Theo ví dụ trên dãy số 2 -3 9 4 -> Có 6 dãy con thỏa mãn yêu cầu: 2 -3; 2 9; -3 4; 9 4; 2 -3 4; 2 9 4.