Little Pandey has N colorless balls. His best friend GJ has K colors, numbered from 1 to K. Little Pandey assigns to GJ the task of coloring each ball, as GJ is a little free these days. For the i-th ball GJ chooses color C_i.

But, Little Pandey is tired and bored after the trip. He decides to find the total number of some special subsets of balls - subsets containing balls of at most M distinct colors. This task is too complicated to handle for Pandey's tired mind, so he asks for your help, since he cannot expect a lot of help from GJ!

Input format:
The first line of the input consists of three integers N, K and M. The next line consists of N integers C₁ , C₂ ... C_N denoting colors of balls.

Output format:
Print the total number of subsets such that each subset contains balls of at most M distinct colors. Output it modulus 10⁹ + 7, i.e., 1000000007.

Constraints:
1 ≤ K, N ≤ 5*10⁵
1≤ M ≤ 10
1 ≤ C_i ≤ K