While Duff was resting in the beach, she accidentally found a strange array b0, b1, ..., bl - 1 consisting of l positive integers. This array was strange because it was extremely long, but there was another (maybe shorter) array, a0, ..., an - 1 that b can be build from a with formula: bi = ai mod n where a mod b denoted the remainder of dividing a by b.

<image>

Duff is so curious, she wants to know the number of subsequences of b like bi1, bi2, ..., bix (0 ≤ i1 < i2 < ... < ix < l), such that: 

  * 1 ≤ x ≤ k
  * For each 1 ≤ j ≤ x - 1, <image>
  * For each 1 ≤ j ≤ x - 1, bij ≤ bij + 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.

Input

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, a0, a1, ..., an - 1 (1 ≤ ai ≤ 109 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, <image>. So all such sequences are: <image>, <image>, <image>, <image>, <image>, <image>, <image>, <image>, <image> and <image>.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

public class D {

	static long MOD = 1000000007;

	static int N, K;
	static long L;
	static long cnt = 0;
	static long[] nlk;
	static int[] a;

	public static void main(String[] args) throws Exception {

		nlk = readLongArray();
		N = (int) nlk[0];
		L = nlk[1];
		K = (int) nlk[2];
		a = readIntArray();

		long whole = L / N;
		long rem = L % N;

		HashMap<Integer, Integer> histWhole = new HashMap<Integer, Integer>();
		for (int i = 0; i < a.length; i++) {
			inc(histWhole, a[i]);
		}

		HashMap<Integer, Integer> histRem = new HashMap<Integer, Integer>();
		for (int i = 0; i < rem; i++) {
			inc(histRem, a[i]);
		}

		int[] distWhole = new int[histWhole.size()];
		int i = 0;
		for (int k : histWhole.keySet()) {
			distWhole[i++] = k;
		}
		Arrays.sort(distWhole);

		int[] distRem = new int[histRem.size()];
		i = 0;
		for (int k : histRem.keySet()) {
			distRem[i++] = k;
		}
		Arrays.sort(distRem);

		long[] current = new long[histWhole.size()];
		for (int j = 0; j < distWhole.length; j++) {
			current[j] = histWhole.get(distWhole[j]);
		}

		long[] currentRem = new long[histRem.size()];
		for (int j = 0; j < distRem.length; j++) {
			currentRem[j] = histRem.get(distRem[j]);
		}

		for (int j = 0; j < currentRem.length; j++) {
			long add = currentRem[j];
			cnt += add;
			cnt %= MOD;
		}

		for (i = 0; i <= K; i++) {

			if ((whole >= i + 1) && (i + 1 <= K)) {
				for (int j = 0; j < current.length; j++) {
					long add = current[j];
					add *= ((whole - i) % MOD);
					add %= MOD;
					cnt += add;
					cnt %= MOD;
				}
			}

			if (rem > 0 && (whole >= i + 1) && (K >= i + 2)) {
				long remCnt = 0;
				for (int j = 0; j < currentRem.length; j++) {
					remCnt += currentRem[j];
				}

				int ci = 0;
				for (int j = 0; j < current.length; j++) {
					while (ci < distRem.length && distRem[ci] < distWhole[j]) {
						remCnt -= currentRem[ci];
						ci++;
					}

					long add = current[j] * remCnt;
					add %= MOD;
					cnt += add;
					cnt %= MOD;
				}
			}

			long[] next = new long[current.length];
			long sum = current[0];
			for (int j = 0; j < next.length; j++) {
				next[j] = sum * histWhole.get(distWhole[j]);
				next[j] %= MOD;

				if (j < next.length - 1) {
					sum += current[j + 1];
					sum %= MOD;
				}
			}

			current = next;
		}

		cnt %= MOD;
		while (cnt < 0)
			cnt += MOD;
		System.out.println(cnt);
	}

	static void inc(HashMap<Integer, Integer> map, int key) {
		if (map.containsKey(key)) {
			map.put(key, map.get(key) + 1);
		} else {
			map.put(key, 1);
		}
	}

	static <T> void print(List<T> v) {
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < v.size(); i++) {
			if (sb.length() > 0) {
				sb.append(' ');
			}

			sb.append(v.get(i));
		}

		System.out.println(sb);
	}

	private static void append(StringBuilder sb, int i) {
		if (sb.length() > 0)
			sb.append('\n');
		sb.append(i);
	}

	static InputStreamReader isr = new InputStreamReader(System.in);
	static BufferedReader br = new BufferedReader(isr);
	static StringBuilder sb = new StringBuilder();

	static String readNextToken() throws IOException {
		sb.setLength(0);
		char c = ' ';
		do {
			c = ((char) br.read());
			if (Character.isWhitespace(c)) {
				if (sb.length() > 0) {
					break;
				}
			} else {
				sb.append(c);
			}
		} while (true);

		return sb.toString();
	}

	static int ni() throws Exception {
		return Integer.parseInt(readNextToken());
	}

	static long nl() throws Exception {
		return Long.parseLong(readNextToken());
	}

	static int[] readIntArray() throws IOException {
		String[] v = br.readLine().split(" ");
		int[] ans = new int[v.length];

		for (int i = 0; i < ans.length; i++) {
			ans[i] = Integer.valueOf(v[i]);
		}

		return ans;
	}

	static long[] readLongArray() throws IOException {
		String[] v = br.readLine().split(" ");
		long[] ans = new long[v.length];

		for (int i = 0; i < ans.length; i++) {
			ans[i] = Long.valueOf(v[i]);
		}

		return ans;
	}

}
