Time-1 - Coconuts of Palm Tree

2 secs 1024 MB
matcharate12's icon matcharate12

AC報酬: 22 ラテコイン

Story

🌴

matcharate君は砂浜を歩いていました。
砂浜にはヤシの木が沢山ありました。matcharate君はその木に実ったヤシの実を収穫している人の姿を見かけました。すると目が合ったのか、話してきました。

「おーい!そこの人!ヤシの実集めを手伝ってくれ!!」

matcharate君は心優しいので手伝ってあげました。そして、話してきた人がこう言ってきました。

「とりあえず...だな、俺はある数字 MM が好きなんだ。だから集めたヤシの実の個数が MM の倍数になるように集めてくれ!!」

問題

砂浜の上に NN 本のヤシの木があります。
それぞれ木は横一列に並んでおり、左から i (1iN)i\ (1\le i\le N) 番目の木には AiA_i 個のヤシの実が実っています。
今からmatcharate君はこれらから異なる 33 本の木を選び、それぞれ選んだ木を揺らし、実ったヤシの実を落としてすべて集めます。

-Mission-
集めたヤシの実の個数が MM の倍数であるようなヤシの木の選び方は何通りあるか。報告せよ。

入力

入力は以下の形式で与えられる。

NNMM
A1A_1A2A_2\dotsANA_N

制約

  • 3N2003\le N\le 200
  • 2M1032\le M\le 10^3
  • 1Ai1061\le A_i\le 10^6
  • 入力はすべて整数

出力

答えを出力せよ。

入出力例

入力例1
4 3
1 2 3 4
出力例1
2

次の 22 通りの選び方が条件を満たします。

  • 1,2,31,2,3 番目の木を選ぶ。合計で 1+2+3=61+2+3=6 個集めることができる。
  • 2,3,42,3,4 番目の木を選ぶ。合計で 2+3+4=92+3+4=9 個集めることができる。

これ以外に条件を満たす選び方は存在しません。

入力例2
3 6
10 10 9
出力例2
0

条件を満たす選び方は存在しません。

入力例3
15 10
3 1 4 1 5 9 2 6 5 3 5 8 9 7 9
出力例3
44

Submit


Go (1.21)