5070: Duff in Beach
内存限制：256 MB
时间限制：2 S
标准输入输出
题目类型：传统
评测方式：文本比较
上传者：
提交：1
通过：1
题目描述
B. Duff in Beach
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
While Duff was resting in the beach, she accidentally found a strange array b0,b1,...,bl-1 consisting of l positive integers. This array was strange because it was extremely long, but there was another (maybe shorter) array, a0,...,an-1 that b can be build from a with formula: bi=ai 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 bi1,bi2,...,bix (0≤i1<i2<...<ix<l), such that:
Duff is not a programmer, and Malek is unavailable at the moment. So she asked for your help. Please tell her this number.
Duff is so curious, she wants to know the number of subsequences of b like bi1,bi2,...,bix (0≤i1<i2<...<ix<l), such that: - 1≤x≤k
-
For each 1≤j≤x-1,
- For each 1≤j≤x-1, bij≤bij+1. i.e this subsequence is non-decreasing.
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≤106 and 1≤l≤1018). The second line contains n space separated integers, a0,a1,...,an-1 (1≤ai≤109 for each 0≤i≤n-1).
Output
Print the answer modulo 1000000007 in one line.
Examples
Input
3 5 3 5 9 1
Output
10
Input
5 10 3 1 2 3 4 5
Output
25
Note
In the first sample case, 
. So all such sequences are: 
, 
, 
, 
, 
, 
, 
, 
, 
and 
. 输入样例 复制
输出样例 复制