Олимпиадный тренинг

Задача . B. Duff на пляже

Задача

Отдыхая на пляже, Duff случайно нашла странный массив b₀, b₁, ..., b_l - 1, состоящий из l положительных целых чисел. Этот массив был странный, потому что он был необычайно длинным, но зато известно, что существует ещё один массив (возможно, короче), a₀, ..., a_n - 1, такой что b построен из a по фомуле: b_i = a_{i mod n}, где a mod b обозначает остаток деления a на b.

$\text{[math]}$

Duff очень хочется узнать число подпоследовательностей b, обладающих следующими свойствами. Пусть b_i₁, b_i₂, ..., b_{i_x} (0 ≤ i₁ < i₂ < ... < i_x < l) — подпоследовательность. Должны быть выполнены следующие свойства:

1 ≤ x ≤ k
Для каждого 1 ≤ j ≤ x - 1, $\text{[math]}$
Для каждого 1 ≤ j ≤ x - 1, b_{i_j} ≤ b_{i_j + 1}, то есть эта последовательность неубывающая.

Так как это число может быть достаточно большим, девушке хочется узнать его остаток от деления на 10⁹ + 7.

Duff не программист, а Malek сейчас недоступен. Итак, она попросила Вашей помощи. Пожалуйста, назовите ей это число.

Входные данные

В первой строке ввода записано три целых числа, n, l и k (1 ≤ n, k, n × k ≤ 10⁶ and 1 ≤ l ≤ 10¹⁸).

Во второй строке записано n целых чисел через пробел, a₀, a₁, ..., a_n - 1 (1 ≤ a_i ≤ 10⁹ для каждого 0 ≤ i ≤ n - 1).

Выходные данные

Выведите ответ по модулю 1 000 000 007.

Примечание

В первом тесте $\text{[math]}$ . Таким образом, все такие последовательности: $\text{[math]}$ , $\text{[math]}$ , $\text{[math]}$ , $\text{[math]}$ , $\text{[math]}$ , $\text{[math]}$ , $\text{[math]}$ , $\text{[math]}$ , $\text{[math]}$ and $\text{[math]}$ .