code-coloring-overdose

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 Ci.

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 C1 , C2 ... CN 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^9 + 7, i.e., 1000000007.

Constraints:
1 ≤ K, N ≤ 5*10^5
1≤ M ≤ 10
1 ≤ Ci ≤ K 

SAMPLE INPUT
4 3 2
3 1 2 3 

SAMPLE OUTPUT
13

Explanation

There are 2^4 = 16 possible subsets and 13 of them satisfy the given condition (a subset must contain balls of at most M = 2 distinct colors).
These 13 subsets are {} , {1} , {2} , {3} , {4} , {1,2} , {1,3} , {1,4} , {1,4,2}  , {1,4,3} , {2,3} , {2,4} , {3,4}  
Numbers in braces denote indices of balls.

Source: hackerearth | Difficulty: MEDIUM
Tags: Dynamic programming

Mathematics


Solutions: