Qatarların izlənməsi 2
Hər gün fermadan sürətli bir qatar keçir. Bu qatarın n vaqonu var və hər biri 1-dən 10^9-a qədər olan təbii ədədlərlə nömrələnib. Fərqli vaqonlar eyni nömrəyə sahib ola bilər.
Adətən Bessi qatarı izləyərək vaqonların nömrələrini qeyd edir. Lakin bu gün hava çox dumanlıdır və Bessi vaqonları görə bilmir! Xoşbəxtlikdən, o, şəhərdəki etibarlı mənbədən vaqon nömrələrinin ardıcıllıqlarının sürüşən pəncərə minimumlarını əldə edib. Xüsusilə, onun k təbii ədədi və n - k + 1 təbii ədədləri c[1], ..., c[n] + 1 − k var, burada c[i] i, i + 1, ..., i + k − 1 vaqonları arasında ən kiçik nömrədir.
Bessiyə vaqonların nömrələrini sürüşən pəncərə minimumlarına uyğun olaraq təyin etməyin neçə yolu olduğunu hesablayın. Bu ədəd çox böyük ola biləcəyi üçün, Bessi onun 10^9 + 7 modulu ilə qalıqını tapmaq istəyir.
Bessinin məlumatı tam etibarlıdır, yəni nömrələrin təyin olunmasının ən azı bir yolu mövcuddur.
Giriş məlumatları
Birinci sətir iki tam ədəddən ibarətdir: n (1 ≤ n ≤ 10^5) və k. Sonrakı sətirdə sürüşən pəncərə minimumları c[1], ..., c[n] + 1 − k verilmişdir.
Çıxış məlumatları
Bir tam ədəd çıxarın: hər vaqona təbii ədəd təyin etməyin yollarının sayı (modul 10^9 + 7 ilə) elə ki, hər 1 ≤ i ≤ n − k + 1 üçün i, i + 1, ..., i + k − 1 vaqonları arasında ən kiçik nömrə c[i] olsun.