Moo Route (Gold)

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Bessie bắt đầu tại vị trí $x = 0$ trên trục số. Trong $T$ giây, mỗi giây cô di chuyển sang trái hoặc phải 1 đơn vị, và cuối cùng quay về $x = 0$ . Cô không bao giờ đi xuống dưới $x = 0$ hoặc vượt quá $x = N$ .

Mảng $A$ ghi lại số lần Bessie đi qua: $A_{0}, A_{1}, \dots, A_{N - 1}$ lần lượt là số lần đi qua $x = 0.5, 1.5, \dots, (N - 1) .5$ .

Đổi hướng xảy ra tại mỗi cặp "LR" hoặc "RL". Hãy đếm số đường đi hợp lệ có số lần đổi hướng tối thiểu, modulo $10^{9} + 7$ .

Dữ liệu vào

Dòng đầu: số nguyên $N$ ( $1 \leq N \leq 10^{5}$ )
Dòng thứ hai: $N$ số nguyên $A_{0}, A_{1}, \dots, A_{N - 1}$ ( $1 \leq A_{i} \leq 10^{6}$ )

Dữ liệu ra

Số đường đi có số lần đổi hướng tối thiểu, modulo $10^{9} + 7$ .

Ràng buộc

$1 \leq N \leq 10^{5}$
$1 \leq A_{i} \leq 10^{6}$

Ví dụ

Input	Output	Giải thích
2 4 6	2	Hai đường đi tối ưu: RRLRLLRRLL và RRLLRRLRLL, cả hai có 5 lần đổi hướng (tối thiểu).

Bình luận

Không có bình luận tại thời điểm này.