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 a clone through alchemy to sit at the study table, but convincing Edward to make a clone of the same height proved impossible. Solving the problem is a better option.