Problem Description

You have $n$ photos, each with an associated happiness value $h_i$, which represents the emotional index when the photo was taken. Now, you need to select a subset of photos (at least one) to put into a machine to generate a memory. The happiness value of this memory is defined as the most frequent element (mode) in the selected sequence of photos$^*$.

Your task is to calculate the number of all possible selection schemes such that the happiness value of the generated memory is exactly $k$. If a photo is selected in one scheme but not selected in another scheme, they are considered different schemes.

$^*$ : The mode of a sequence is the element that occurs the most frequently in that sequence.

Input Format

The first line contains two integers $n$ and $k$, representing the number of photos and the target happiness value for the memory.

The second line contains $n$ integers $h_i$, representing the happiness value of each photo.

Output Format

Output an integer representing the number of selection schemes that meet the condition, modulo $10^9 + 7$ since the result may be very large.

Example

Example Input 1

3 3
1 3 5

Example Output 1

2

Example Input 2

11 4
5 1 4 1 9 1 9 8 10 4 4

Example Output 2

772

Constraints

$1 \leq k \leq n \leq 5 \times 10^3$

$1 \leq h_i \leq n$