Problem Description

There are $ N $ rest stops around a lake.
The rest stops are numbered clockwise from $1, 2, \dots, N$.
It takes $ A_i $ steps to walk clockwise from rest stop $ i $ to rest stop $ i+1 $ (where rest stop $ N+1 $ refers to rest stop $ 1 $).
The minimum number of steps to walk clockwise from rest stop $ s $ to rest stop $ t $ (where $s \neq t$) is a multiple of $ M $.
Find the number of possible pairs $ (s, t) $.

Input Format

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

$ N $ $ M $ $ A_1 $ $ A_2 $ $\dots$ $ A_N $

Output Format

Output the answer as an integer.

Sample Input and Output

Sample Input #1

4 3
2 1 4 3

Sample Output #1

4

Sample Input #2

2 1000000
1 1

Sample Output #2

0

Sample Input #3

9 5
9 9 8 2 4 4 3 5 3

Sample Output #3

11

Notes/Hints

Constraints

• All inputs are integers.
• $2 \le N \le 2 \times 10^5$
• $1 \le A_i \le 10^9$
• $1 \le M \le 10^6$

Sample Explanation 1

• The minimum number of steps to walk clockwise from rest stop $ 1 $ to rest stop $ 2 $ is $ 2 $ steps, which is not a multiple of $ 3 $.
• The minimum number of steps to walk clockwise from rest stop $ 1 $ to rest stop $ 3 $ is $ 3 $ steps, which is a multiple of $ 3 $.
• The minimum number of steps to walk clockwise from rest stop $ 1 $ to rest stop $ 4 $ is $ 7 $ steps, which is not a multiple of $ 3 $.
• The minimum number of steps to walk clockwise from rest stop $ 2 $ to rest stop $ 3 $ is $ 1 $ step, which is not a multiple of $ 3 $.
• The minimum number of steps to walk clockwise from rest stop $ 2 $ to rest stop $ 4 $ is $ 5 $ steps, which is not a multiple of $ 3 $.
• The minimum number of steps to walk clockwise from rest stop $ 2 $ to rest stop $ 1 $ is $ 8 $ steps, which is not a multiple of $ 3 $.
• The minimum number of steps to walk clockwise from rest stop $ 3 $ to rest stop $ 4 $ is $ 4 $ steps, which is not a multiple of $ 3 $.
• The minimum number of steps to walk clockwise from rest stop $ 3 $ to rest stop $ 1 $ is $ 7 $ steps, which is not a multiple of $ 3 $.
• The minimum number of steps to walk clockwise from rest stop $ 3 $ to rest stop $ 2 $ is $ 9 $ steps, which is a multiple of $ 3 $.
• The minimum number of steps to walk clockwise from rest stop $ 4 $ to rest stop $ 1 $ is $ 3 $ steps, which is a multiple of $ 3 $.
• The minimum number of steps to walk clockwise from rest stop $ 4 $ to rest stop $ 2 $ is $ 5 $ steps, which is not a multiple of $ 3 $.
• The minimum number of steps to walk clockwise from rest stop $ 4 $ to rest stop $ 3 $ is $ 6 $ steps, which is a multiple of $ 3 $.

Thus, the number of pairs $ (s, t) $ is $ 4 $.

见题面 Input 部分

见题面 Output 部分