Subsets Divisible by K

You are given a set of N integers and an integer K. Your task is to count the number of subsets (including the empty subset) such that the sum of the elements in each subset is divisible by K. Since the answer can be very large, output the result modulo \(10^9+7\).

Input Format:

• The first line contains two integers N and K.
• The second line contains N space-separated integers representing the set elements.

Output Format:

• Output a single integer, the number of subsets whose sum is divisible by K modulo \(10^9+7\).

Note: The empty subset is also considered.

inputFormat

The input is read from standard input (stdin). The first line contains two integers N and K. The second line contains N integers separated by spaces.

outputFormat

Output a single integer to standard output (stdout) representing the number of valid subsets modulo \(10^9+7\).

## sample

3 3
1 2 3

4

</p>