Theo Dõi Chuyến Tàu 2

Điểm: 1,00 (OI)

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

Python 3 5.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

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 \leq a [i] \leq 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 \leq i \leq 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 \leq K \leq N \leq 100 000$ )
$N - K + 1$ dòng tiếp theo, dòng thứ $i$ gồm một số nguyên $c [i]$ ( $1 \leq c [i] \leq 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 \leq K \leq N \leq 100 000$
$1 \leq c [i] \leq 10^{9}$
Dữ liệu đảm bảo tồn tại ít nhất một mảng hợp lệ

Ví dụ

Input	Output	Giải thích
4 2 999999998 999999999 999999998	3	$N = 4$ , $K = 2$ , mảng $c = [999999998, 999999999, 999999998]$ . Ba mảng hợp lệ là: $[999999998, 10^{9}, 999999999, 999999998]$ , $[999999998, 999999999, 10^{9}, 999999998]$ , $[999999998, 999999999, 999999999, 999999998]$ .

Bình luận

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