YSACODE discuss3

While Duff was resting in the beach, she accidentally found a strange array b₀,b₁,...,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₀,...,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.

$\text{[math]}$

Duff is so curious, she wants to know the number of subsequences of b like b_i₁,b_i₂,...,b_{i_x} (0≤i₁<i₂<...<i_x<l), such that:

1≤x≤k
For each 1≤j≤x-1, $\text{[math]}$
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 10⁹+7.

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

Input

The first line of input contains three integers, n,l and k (1≤n,k, n×k≤10⁶ and 1≤l≤10¹⁸).

The second line contains n space separated integers, a₀,a₁,...,a_n-1 (1≤a_i≤10⁹ for each 0≤i≤n-1).

Output

Print the answer modulo 1000000007 in one line.

Examples

Input

3 5 3
5 9 1

Output

Input

5 10 3
1 2 3 4 5

Output

Note

In the first sample case, $\text{[math]}$ . So all such sequences are: $\text{[math]}$ , $\text{[math]}$ , $\text{[math]}$ , $\text{[math]}$ , $\text{[math]}$ , $\text{[math]}$ , $\text{[math]}$ , $\text{[math]}$ , $\text{[math]}$ and $\text{[math]}$ .

2264: Duff in Beach

Description

Source/Category