Theo Dõi Chuyến Tàu 2

Một chuyến tàu có $N$ toa, mỗi toa mang một nhãn số nguyên dương không vượt quá ${10}^9$. Farmer John đã ghi lại mảng $c[1],c[2],\dots ,c[N-K+1]$, trong đó $c[i]$ là giá trị nhỏ nhất trong số các nhãn của $K$ toa liên tiếp từ toa $i$ đến toa $i+K-1$.

Hãy đếm số mảng nhãn $a[1],a[2],\dots ,a[N]$ hợp lệ thỏa mãn:

• $1\le a[i]\le {10}^9$ với mọi $i$
• $min(a[i],a[i+1],\dots ,a[i+K-1])=c[i]$ với mọi $1\le i\le N-K+1$

Đưa ra kết quả modulo ${10}^9+7$.

Dữ liệu vào

• Dòng đầu: hai số nguyên $N$ và $K$ ($1\le K\le N\le 100000$)
• $N-K+1$ dòng tiếp theo, dòng thứ $i$ gồm một số nguyên $c[i]$ ($1\le c[i]\le {10}^9$)

Dữ liệu ra

Một số nguyên: số mảng hợp lệ modulo ${10}^9+7$.

Ràng buộc

• $1\le K\le N\le 100000$
• $1\le c[i]\le {10}^9$
• Dữ liệu đảm bảo tồn tại ít nhất một mảng hợp lệ

Ví dụ