B. Дуфф далайн эрэг дээр

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Дуфф далайн эрэг дээр амарч байхдаа санаандгүй $l$ эерэг бүхэл тоонуудаас бүрдэх үл мэдэгдэх $b_{0}, b_{1}, ..., b_{l - 1}$ массив олжээ. Энэ массив нь маш урт байсан учир үл мэдэгдэж байсан гэвч тэнд бас нэг массив (богино байж магадгүй) байсан. Энэ нь $b_{i} = a_{i mod n}$ (энд $a mod b$ нь $a$-г $b$-д хуваагаад гарсан үлдэгдийг заана) томъёогоор $a$-аас $b$-г байгуулж болохоор $a_{0}, ..., a_{n - 1}$ массив байсан.

Дуфф их сониуч бөгөөд $b$-ийн $b_{i_{1}}, b_{i_{2}}, ..., b_{i_{x}}$ ($0 ≤ i_{1} < i_{2} < ... < i_{x} < l$) иймэрхүү дэд дарааллуудын тоог мэдэхийг хүсч байна. Мөн дэд дараалал нь:

  • $1 ≤ x ≤ k$
  • $1 ≤ j ≤ x - 1$ бүрийн хувьд
  • $1 ≤ j ≤ x - 1$ бүрийн хувьд $b_{i_{j}} ≤ b_{i_{j + 1}}$ буюу дэд дараалал нь буурахгүй байх ёстой.

Энэ тоо нь маш том байж болох учир Дуфф $10^{9} + 7$-д хуваагаад гарсан үлдэгдлийг нь мэдэхийг хүсч байна.

Дуфф програмчлагч биш ба Малек одоогоор эзгүй байгаа. Тэр таныг туслахыг хүсэж байгаа учир түүнд уг тоог олоход туслана уу.

Оролт

Оролтын эхний мөрөнд гурван бүхэл тоон утга $n, l$ болон $k$ ($1 ≤ n, k$, $n × k ≤ 10^{6}$ ба $1 ≤ l ≤ 10^{18}$) байна.

Хоёр дахь мөрөнд зайгаар тусгаарлагдсан $n$ бүхэл тоон утга $a_{0}, a_{1}, ..., a_{n - 1}$ ($0 ≤ i ≤ n - 1$ бүрийн хувьд $1 ≤ a_{i} ≤ 10^{9}$) байна.

Гаралт

Гаралтанд $1 000 000 007$ тоонд хуваагаад гарсан үлдэгдлийг нэг мөрөнд хэвлэ.

Орчуулсан: Г.Мэндбаяр

Жишээ тэстүүд

Оролт
3 5 3
5 9 1
Гаралт
10
Оролт
5 10 3
1 2 3 4 5
Гаралт
25

Тэмдэглэл

Эхний жишээн дээр . Бүх дэд дараалал нь: , , , , , , , , болон .

Сэтгэгдлүүдийг ачааллаж байна...