Giờ thể dục

Trong giờ thể dục, $N$ học sinh xếp thành một hàng, học sinh thứ $i$ (tính từ trái sang) cầm quả bóng số $i$. Các quả bóng được đánh số từ $1$ đến $N$.

Bài khởi động gồm nhiều lượt ném. Ở mỗi lượt, giáo viên chọn hai học sinh khác nhau bất kỳ, hai người này ném bóng cho nhau: vị trí đứng không đổi, chỉ có hai quả bóng đổi chỗ.

Mỗi học sinh $i$ có giới hạn $t_i$ là số lượt ném tối đa mà em đó được tham gia, với $t_i$ bằng $1$ hoặc $2$.

Sau khi bài khởi động kết thúc, "thứ tự bóng" là dãy $N$ số trong đó số thứ $i$ là số hiệu quả bóng mà học sinh thứ $i$ đang cầm. Hãy đếm số thứ tự bóng khác nhau có thể thu được, lấy dư theo modulo ${10}^9+7$.

Dữ liệu vào

• Dòng đầu chứa số nguyên $N$: số học sinh.
• Dòng thứ hai chứa $N$ số nguyên $t_1,t_2,\dots ,t_N$ ($t_i\in \{1,2\}$): giới hạn số lượt ném của từng học sinh.

Dữ liệu ra

In ra một số nguyên duy nhất: số thứ tự bóng khác nhau có thể thu được, theo modulo ${10}^9+7$.

Ràng buộc

• $1\le N\le {10}^6$
• $t_i\in \{1,2\}$ với mọi $i$

Ví dụ