Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

No tag edit access

B. Duff in Beach

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputWhile 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} < *i*_{2} < ... < *i*_{x} < *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.

Input

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).

Output

Print the answer modulo 1 000 000 007 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 .

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/12/2018 00:31:28 (f2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|