743. Concerned Guardian

0

Medium

Alphonse and Edward live with Pinako and Winry after their mother's passing. Pinako is concerned about their focus on alchemy and lack of attention to their studies.

To improve their math skills, Pinako gives them a daily problem to solve. They can only practice alchemy after solving the problem. Help them solve the given problem so they can start their alchemy practice early today.

Given an array A of N non-negative integers and two integers K and M, find the number of subsequences of array A with length K that satisfy the following property: for all i such that 1≤i≤K, Si%M=i%M, where Si is the i-th element of the subsequence (using 1-based indexing).

As the number of subsequences may be very large, output the answer modulo 1000000007.

Note: We considered creating an alchemy clone to solve the problem, but convincing Edward to create a clone of his exact height proved impossible. Therefore, solving the problem is the better option.

Input Format

Output Format

^{9}+7.

Example

Input

Output

Constraints

1≤N≤104

1≤K≤N

ceil(K/100) ≤ M ≤ 100×K

0≤Ai≤10

^{9}

View Submissions

Console