Duff in Beach

题意翻译

### 题目翻译 给出一个长度为$n$的序列$a_0,a_1,...,a_{n-1}$，通过它构造出一个长度为$l$的序列$b_0,b_1,...,b_{l-1}$满足$b_i = a_{i \mod n}$。 现求满足如下条件的$b$的子序列$b_{q_0} , b_{q_1},...,b_{q_{x-1}}$的数量： 1、$1 \leq x \leq k$ 2、$\forall i \in [0,x-2] , \lfloor\frac{q_i}{n} \rfloor = \lfloor \frac{q_{i+1}}{n} \rfloor -1$ 3、$\forall i \in [0,x-2] , b_{q_i} \leq b_{q_{i+1}}$ ### 输入格式 第一行三个正整数 $n,l,k$（$n k \leq 10^6$，$l \leq {10}^{18}$）。 接下来一行 $n$ 个正整数 $a_i$（$a_i \leq {10}^9$）描述序列。 ### 输出格式 一行一个正整数表示答案模$10^9+7$。

题目描述

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_{i1},b_{i2},...,b_{ix} $ ( $ 0<=i_{1}&lt;i_{2}&lt;...&lt;i_{x}&lt;l $ ), such that: - $ 1<=x<=k $ - For each $ 1<=j<=x-1 $ ,  - For each $ 1<=j<=x-1 $ , $ b_{ij}<=b_{ij+1} $ . i.e this subsequence is non-decreasing. Since this number can be very large, she want to know it modulo $ 10^{9}+7 $ . Duff is not a programmer, and Malek is unavailable at the moment. So she asked for your help. Please tell her this number.

输入输出格式

输入格式

The first line of input contains three integers, $ n,l $ and $ k $ ( $ 1<=n,k $ , $ n×k<=10^{6} $ and $ 1<=l<=10^{18} $ ). The second line contains $ n $ space separated integers, $ a_{0},a_{1},...,a_{n-1} $ ( $ 1<=a_{i}<=10^{9} $ for each $ 0<=i<=n-1 $ ).

输出格式

Print the answer modulo $ 1000000007 $ in one line.

输入输出样例

输入样例 #1

3 5 3
5 9 1

输出样例 #1

10

输入样例 #2

5 10 3
1 2 3 4 5

输出样例 #2

25

说明

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