题目描述

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.

说明

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

dp 但是因为是在每个块内dp所以滕老师就选过来了？数据范围让我第一眼以为n^2过百万？

dp[i][j] = ∑dp[i-1][z] && z <= j