CF587B.Duff in Beach

While Duff was resting in the beach, she accidentally found a strange array _b_0, _b_1, ..., b__l - 1 consisting of l positive integers. This array was strange because it was extremely long, but there was another (maybe shorter) array, _a_0, ..., a__n - 1 that b can be build from a with formula: b__i = a__i mod n where a mod b denoted the remainder of dividing a by b.

Duff is so curious, she wants to know the number of subsequences of b like _b__i_1, _b__i_2, ..., b__i__x (0 ≤ _i_1 < _i_2 < ... < i__x < l), such that:

• 1 ≤ x ≤ k
• For each 1 ≤ j ≤ x - 1,
• For each 1 ≤ j ≤ x - 1, b__i__j ≤ b__i__j + 1. i.e this subsequence is non-decreasing.

Since this number can be very large, she want to know it modulo 109 + 7.

Duff is not a programmer, and Malek is unavailable at the moment. So she asked for your help. Please tell her this number.

当达芙在海滩休息时，偶然发现了一个奇怪的数组 $b_0, b_1, \dots, b_{l-1}$，它由 $l$ 个正整数组成。这个数组之所以奇怪，是因为它极其长；但存在另一个（可能更短的）数组 $a_0, a_1, \dots, a_{n-1}$，使得数组 $b$ 可由 $a$ 按如下公式构造：

$$b_i = a_{i \bmod n},$$

其中 $a \bmod b$ 表示 $a$ 除以 $b$ 的余数。

达芙非常好奇，她想知道数组 $b$ 中满足如下条件的子序列 $b_{i_1}, b_{i_2}, \dots, b_{i_x}$（其中 $0 \le i_1 < i_2 < \dots < i_x < l$）的个数：

• $1 \le x \le k$；
• 对每个 $1 \le j \le x-1$，有 ；
• 对每个 $1 \le j \le x-1$，有 $b_{i_j} \le b_{i_{j+1}}$，即该子序列是非递减的。

由于该数目可能非常大，她希望得到其对 $10^9 + 7$ 取模的结果。

达芙不是程序员，而马莱克此刻又无法联系上。因此她向你求助，请你告诉她这个数。

The first line of input contains three integers, n, l and k (1 ≤ n, k, n × k ≤ 106 and 1 ≤ l ≤ 1018).

The second line contains n space separated integers, _a_0, _a_1, ..., a__n - 1 (1 ≤ a__i ≤ 109 for each 0 ≤ i ≤ n - 1).

输入的第一行包含三个整数 $n$、$l$ 和 $k$（满足 $1 \leq n, k, n \times k \leq 10^6$ 且 $1 \leq l \leq 10^{18}$）。

第二行包含 $n$ 个用空格分隔的整数 $a_0, a_1, \dots, a_{n-1}$（对每个 $0 \leq i \leq n-1$，满足 $1 \leq a_i \leq 10^9$）。

Print the answer modulo 1 000 000 007 in one line.

在一行中输出对 $1\,000\,000\,007$ 取模后的答案。

In the first sample case, . So all such sequences are: , , , , , , , , and .

在第一个样例中，。因此所有满足条件的序列是：、、、、、、、、 和 。