Mỗi ngày, đoàn tàu tốc hành chạy ngang qua trang trại. Tàu có \(N\) toa (\(1 \leq N \leq 10^5\)), mỗi toa mang một nhãn là số nguyên dương từ \(1\) đến \(10^9\); các toa khác nhau có thể mang cùng một nhãn.

Thông thường, Bessie quan sát đoàn tàu chạy qua và ghi lại nhãn của các toa. Nhưng hôm nay trời quá nhiều sương mù, Bessie không thể nhìn thấy bất kỳ nhãn nào! May mắn thay, cô đã lấy được các giá trị nhỏ nhất trên cửa sổ trượt của dãy nhãn toa tàu từ một nguồn đáng tin cậy trong thành phố. Cụ thể, cô có một số nguyên dương \(K\) và \(N-K+1\) số nguyên dương \(c_1, \dots, c_{N+1-K}\), trong đó \(c_i\) là nhãn nhỏ nhất trong các toa \(i, i+1, \dots, i+K-1\).

Hãy giúp Bessie tìm số cách gán nhãn cho mỗi toa sao cho phù hợp với các giá trị nhỏ nhất trên cửa sổ trượt. Vì số này có thể rất lớn, Bessie chấp nhận phần dư của nó theo modulo \(10^9 + 7\).

Thông tin của Bessie hoàn toàn đáng tin cậy; nói cách khác, dữ liệu bảo đảm có ít nhất một cách gán nhãn phù hợp.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên \(N\) và \(K\) cách nhau bởi dấu cách. Các dòng tiếp theo chứa lần lượt các giá trị nhỏ nhất trên cửa sổ trượt \(c_1, \dots, c_{N+1-K}\), mỗi dòng một giá trị.

Dữ liệu ra

In ra một số nguyên duy nhất: số cách gán cho mỗi toa một số nguyên dương không vượt quá \(10^9\) sao cho nhãn nhỏ nhất trong các toa \(i, i+1, \dots, i+K-1\) là \(c_i\) với mọi \(1 \leq i \leq N-K+1\), lấy theo modulo \(10^9 + 7\).

Ví dụ

4 2
999999998
999999999
999999998

3

Nguồn

Đề bài gốc: USACO 2019 January Contest, Platinum — Train Tracking 2

Tác giả: Dhruv Rohatgi