当达夫在海滩休息时,她无意中发现了一个奇怪的数组 b0, b1, ..., bl - 1,由 l 个正整数组成。这个数组很奇怪,因为它非常长,但还有另一个(可能更短)数组 a0, ..., an - 1,b 可以通过 a 构建,公式为:bi = ai mod n,其中 a mod b 表示 a 除以 b 的余数。
Duff 很好奇,她想知道 b 像 bi1, bi2, ..., bix (0 ≤ i1 < i2 < ... < ix < l) 这样的子序列的数量,这样:
- 1 ≤ x ≤ k
- 对于每个 1 ≤ j ≤ x - 1,$$\left\lfloor \frac { i j } { n } \right\rfloor + 1 = \left\lfloor \frac { i j + 1 } { n } \right\rfloor$$
- 对于每个 1 ≤ j ≤ x - 1,bij ≤ bij + 1,即该子序列是非递减的。
由于这个数字可能非常大,她想知道它对 109 + 7 的模。
Duff 不是程序员,Malek 目前没空。所以她请求你的帮助。请告诉她这个号码。
输入
输入的第一行包含三个整数 n、l 和 k(1 ≤ n、k、n × k ≤ 106 和 1 ≤ l ≤ 1018)。
第二行包含 n 个空格分隔的整数 a0、a1、...、an - 1(对于每个 0 ≤ i ≤ n - 1,1 ≤ ai ≤ 109)。
输出
将答案以 1 000 000 007 为模打印在一行中。
示例
输入 #1
3 5 3 5 9 1
输出 #1
10
输入 #2
5 10 3 1 2 3 4 5
输出 #2
25
注意
在第一个示例中,$$b = \langle 5, 9, 1, 5, 9 \rangle$$。所以所有这样的序列是: $$\langle b_{0}\rangle=\langle5\rangle$$, $$\langle b_{1}\rangle=\langle9\rangle$$, $$\langle b_{2}\rangle=\langle1\rangle$$, $$\langle b_{3}\rangle=\langle5\rangle$$, $$\langle b_{4}\rangle=\langle9\rangle$$, $${ \langle b _ { 0 }, b _ { 3 } \rangle = \langle 5, 5 \rangle }$$, $${ \langle b _ { 0 }, b _ { 4 } \rangle = \langle 5, 9 \rangle }$$, $${ \langle b _ { 1 }, b _ { 4 } \rangle = \langle 9, 9 \rangle }$$, $${ \langle b _ { 2 }, b _ { 3 } \rangle = \langle 1, 5 \rangle }$$ 和 $${ \langle b _ { 2 }, b _ { 4 } \rangle = \langle 1, 9 \rangle }$$。