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.math.*;
import java.io.*;
import java.util.*;
public class C588D{
   public static long[] cAr, div;
   public static int N,M,K;
   public static int[] numCycle;
   public static Map<Integer,Set<Integer>> map;
   public static long MOD = 1000000007;
   public static void main(String[] args) throws IOException{
      InputReader in=new InputReader(new InputStreamReader(System.in));
      PrintWriter out=new PrintWriter(new BufferedOutputStream(System.out));
      long[] ar1=in.nextLongAr();
      long N=ar1[0];
      long L=ar1[1];
      long K=ar1[2];
      long[] ar=in.nextLongAr();
      long[] dar=new long[(int)N];
      
      if(K==1) System.out.println(L%MOD);
      
      else{
         TreeMap<Long,Set<Integer>> map=new TreeMap<Long,Set<Integer>>();
         for(int x=0;x<N;x++){
            long t=ar[x];
            Set<Integer> set=new HashSet<Integer>();
            if(map.keySet().contains(t)) set=map.get(t);
            set.add(x);
            map.put(t,set);
         }
         
         for(int x=0;x<N;x++) dar[x]=1;
      
         long M=L%N;
         long div=(L/N)%MOD;
         long total=0;
         for(int x=0;x<K;x++){
            long addSmall=0;
            long addBig=0;
            for(int y=0;y<N&&(x*N+y<L);y++){
               if(y>=M) addSmall+=dar[y];
               else addBig+=dar[y];
            }
            addSmall=addSmall%MOD;
            addBig=addBig%MOD;
            total=(total+addSmall*(div-x))%MOD;
            total=(total+addBig*(div-x+1))%MOD;
         
            long t=0;
            if(x<K-1)
               for(long i:map.keySet()){
                  for(int j:map.get(i)){
                     t=(t+dar[j]*map.get(i).size())%MOD;
                     break;}
               
                  for(int j:map.get(i))
                     dar[j]=t;
               }
         }
         
         total=total%MOD;
         if(total<0) total+=MOD;
         System.out.println(total);
      }
   }
   
   public static void setUpChoose(int t){
      cAr=new long[t+1];
      div=new long[t+1];
      cAr[0]=1;
      div[0]=1;
      
      for(int x=1;x<=t;x++){
         cAr[x]=(x*cAr[x-1])%(MOD);
         div[x]=pow(cAr[x],MOD-2);} 
   }
   
   public static long choose(int x,int y){
      long a=cAr[x+y];
      long b=div[x];
      long c=div[y];
      a=(a*b)%MOD;
      a=(a*c)%MOD;
      return a;
   } 
   
   public static long pow(long a,long b){
      if(b==1) 
         return a;
      long c=b/2;
      long temp=pow(a,c)%MOD;
      temp=(temp*temp)%MOD;
      if(b%2==1) temp=temp*a;
      return temp%MOD;
   }
}

class InputReader{
   private BufferedReader br;
   public InputReader(InputStreamReader in){
      br=new BufferedReader(in);
   }
   public int nextInt(){
      try{
         return Integer.parseInt(br.readLine());}
      catch(IOException e){throw new InputMismatchException();}
   }
   public int[] nextIntAr(){
      try{
         String[] s=br.readLine().split(" ");
         int[] ret=new int[s.length];
         for(int x=0;x<s.length;x++)
            ret[x]=Integer.parseInt(s[x]);
         return ret;}
      
      catch(IOException e){throw new InputMismatchException();}
   }
   
   public long nextLong(){
      try{
         return Long.parseLong(br.readLine());}
      catch(IOException e){throw new InputMismatchException();}
   }
   public long[] nextLongAr(){
      try{
         String[] s=br.readLine().split(" ");
         long[] ret=new long[s.length];
         for(int x=0;x<s.length;x++)
            ret[x]=Long.parseLong(s[x]);
         return ret;}
      
      catch(IOException e){throw new InputMismatchException();}
   }

   public String[] nextStringAr(){
      try{
         return br.readLine().split(" ");}
      
      catch(IOException e){throw new InputMismatchException();}
   }
   
   public String nextString(){
      try{
         return br.readLine();}
      
      catch(IOException e){throw new InputMismatchException();}
   }
}