Duff in Beach
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**i*1,<=*b**i*2,<=...,<=*b**i**x* (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**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 109<=+<=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*<=≤<=106 and 1<=≤<=*l*<=≤<=1018).

The second line contains *n* space separated integers, *a*0,<=*a*1,<=...,<=*a**n*<=-<=1 (1<=≤<=*a**i*<=≤<=109 for each 0<=≤<=*i*<=≤<=*n*<=-<=1).
Print the answer modulo 1<=000<=000<=007 in one line.
In the first sample case, <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/d9d8fe92937aeef2bcddb9d213e5587f0f950087.png" style="max-width: 100.0%;max-height: 100.0%;"/>. So all such sequences are: <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/54d7dd513b50dae3415992b37dcf6f8ff2f24a73.png" style="max-width: 100.0%;max-height: 100.0%;"/>, <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/fcd7414fd5b0b1459adc9dafca95e6d5a23b0d7d.png" style="max-width: 100.0%;max-height: 100.0%;"/>, <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/f6d2e0d0317c10a3c5213068fb1d1e1f53ff26eb.png" style="max-width: 100.0%;max-height: 100.0%;"/>, <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/8f6627cad3dd113f47d84a1226f30fe423939757.png" style="max-width: 100.0%;max-height: 100.0%;"/>, <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/c6db71d99107f752b5caa1ba7e44af1d2302e5db.png" style="max-width: 100.0%;max-height: 100.0%;"/>, <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/a06ffb7bf9126fd634a790703c0bbfda00c60aa1.png" style="max-width: 100.0%;max-height: 100.0%;"/>, <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/b086d545b6c80640ea8558920709e3c51ba3bf43.png" style="max-width: 100.0%;max-height: 100.0%;"/>, <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/661b7811fccac48a9e96733bc99c3dfec93ad6d7.png" style="max-width: 100.0%;max-height: 100.0%;"/>, <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/8756896f0d00888771e69f1a9ccddeee19d4a9ab.png" style="max-width: 100.0%;max-height: 100.0%;"/> and <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/e771f8119b1b8218c875759aa03e38312514c9a2.png" style="max-width: 100.0%;max-height: 100.0%;"/>.