← 返回题目列表

Codeforces · 587/B

B. 达夫在海滩

中文机器翻译题面 查看原题

当达夫在海滩休息时,她无意中发现了一个奇怪的数组 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 }$$。