Subarray Sums Divisibility

Given q queries, each query provides an array of integers and a divisor p. For each query, determine the number of contiguous subarrays (i.e. segments) whose sum is divisible by p. Since the answer might be large, output it modulo \(10^9+7\).

The problem can be solved efficiently using prefix sums and counting the frequency of remainders modulo p. A subarray sum from index i to j is divisible by p if the prefix sum modulo values at positions i and j+1 are equal.

inputFormat

The input is read from stdin and has the following format:

• The first line contains a single integer q, the number of queries.
• For each query, the first line contains two integers n and p where n is the length of the array and p is the divisor.
• The next line contains n space-separated integers representing the elements of the array.

outputFormat

For each query, output a single line to stdout containing one integer — the number of subarrays whose sum is divisible by p, modulo \(10^9+7\).

## sample

1
4 5
5 10 15 20

10

</p>