Problem Description

Anmichi received a sequence \( A \) of length \( N \) as a birthday present. He likes the number \( D \), so he wants to find combinations of \( (l, r) \) where both the sum and the product of the subsequence \( A_l, A_{l+1}, \ldots, A_r \) (with \( 1 \leq l \leq r \leq N \)) are multiples of \( D \). Determine the number of such combinations.

Input Format

The input is given from the standard input in the following format:

\( N \) \( D \)
\( A_1 \) \( A_2 \) \( \ldots \) \( A_N \)

Output Format

Output the number of combinations \( (l, r) \) where both the sum and the product of the subsequence \( A_l, A_{l+1}, \ldots, A_r \) (with \( 1 \leq l \leq r \leq N \)) are multiples of \( D \).

Sample Input and Output

Sample Input #1

5 3
1 2 1 3 2

Sample Output #1

4

Sample Input #2

5 3
8 6 9 1 20

Sample Output #2

6

Sample Input #3

8 1
1 10 100 1000 10000 1000000 10000000 100000000

Sample Output #3

36

Notes/Hints

Constraints

• All inputs are integers.
• \( 1 \leq N \leq 10^5 \)
• \( 1 \leq D \leq 10^9 \)
• \( 1 \leq A_i \leq 10^9 \)

见题面 Input 部分

见题面 Output 部分