AT_abc367_d [ABC367D] Pedometer

[problemUrl]: https://atcoder.jp/contests/abc367/tasks/abc367_d 湖の周りに $ N $ 個の休憩所があります。 休憩所には時計回りに $ 1,2,\dots,N $ の番号が付いています。 休憩所 $ i $ から休憩所 $ i+1 $ まで時計回りに歩くには $ A_i $ 歩かかります ( 但し、休憩所 $ N+1 $ は休憩所 $ 1 $ を指します ) 。 休憩所 $ s $ から休憩所 $ t $ ( $ s\ \neq\ t $ ) まで時計回りに歩くのにかかる最小の歩数は $ M $ の倍数でした。 $ (s,t) $ の組として考えられるものの数を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ A_1 $ $ A_2 $ $ \dots $ $ A_N $

答えを整数として出力せよ。

### 制約 - 入力は全て整数 - $ 2\ \le\ N\ \le\ 2\ \times\ 10^5 $ - $ 1\ \le\ A_i\ \le\ 10^9 $ - $ 1\ \le\ M\ \le\ 10^6 $ ### Sample Explanation 1 \- 休憩所 $ 1 $ から休憩所 $ 2 $ まで時計回りに歩くのにかかる最小の歩数は $ 2 $ 歩で、これは $ 3 $ の倍数ではありません。 - 休憩所 $ 1 $ から休憩所 $ 3 $ まで時計回りに歩くのにかかる最小の歩数は $ 3 $ 歩で、これは $ 3 $ の倍数です。 - 休憩所 $ 1 $ から休憩所 $ 4 $ まで時計回りに歩くのにかかる最小の歩数は $ 7 $ 歩で、これは $ 3 $ の倍数ではありません。 - 休憩所 $ 2 $ から休憩所 $ 3 $ まで時計回りに歩くのにかかる最小の歩数は $ 1 $ 歩で、これは $ 3 $ の倍数ではありません。 - 休憩所 $ 2 $ から休憩所 $ 4 $ まで時計回りに歩くのにかかる最小の歩数は $ 5 $ 歩で、これは $ 3 $ の倍数ではありません。 - 休憩所 $ 2 $ から休憩所 $ 1 $ まで時計回りに歩くのにかかる最小の歩数は $ 8 $ 歩で、これは $ 3 $ の倍数ではありません。 - 休憩所 $ 3 $ から休憩所 $ 4 $ まで時計回りに歩くのにかかる最小の歩数は $ 4 $ 歩で、これは $ 3 $ の倍数ではありません。 - 休憩所 $ 3 $ から休憩所 $ 1 $ まで時計回りに歩くのにかかる最小の歩数は $ 7 $ 歩で、これは $ 3 $ の倍数ではありません。 - 休憩所 $ 3 $ から休憩所 $ 2 $ まで時計回りに歩くのにかかる最小の歩数は $ 9 $ 歩で、これは $ 3 $ の倍数です。 - 休憩所 $ 4 $ から休憩所 $ 1 $ まで時計回りに歩くのにかかる最小の歩数は $ 3 $ 歩で、これは $ 3 $ の倍数です。 - 休憩所 $ 4 $ から休憩所 $ 2 $ まで時計回りに歩くのにかかる最小の歩数は $ 5 $ 歩で、これは $ 3 $ の倍数ではありません。 - 休憩所 $ 4 $ から休憩所 $ 3 $ まで時計回りに歩くのにかかる最小の歩数は $ 6 $ 歩で、これは $ 3 $ の倍数です。 以上より、求めるべき $ (s,t) $ の組の数は $ 4 $ 個です。