配点 : $300$ 点

問題文

高橋君は、$N$ 枚のカードを持っています。 $i \, (1 \leq i \leq N)$ 番目のカードには、整数 $x_i$ が書かれています。 高橋君は、これらのカードの中から $1$ 枚以上を選び、 選んだカードに書かれた整数の平均をちょうど $A$ にしたいと考えています。 そのようなカードの選び方が何通りあるか求めてください。

制約

• $1 \leq N \leq 50$
• $1 \leq A \leq 50$
• $1 \leq x_i \leq 50$
• $N,\,A,\,x_i$ はいずれも整数である

部分点

• $1 \leq N \leq 16$ を満たすデータセットに正解した場合は、$200$ 点が与えられる。

入力

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

$N$ $A$

$x_1$ $x_2$ $...$ $x_N$

出力

書かれた整数の平均がちょうど $A$ となるようなカードの選び方の総数を出力せよ。

4 8
7 9 8 9

5

• 平均が $8$ となるカードの選び方は、以下の $5$ 通りです。- $3$ 枚目のカードのみを選ぶ。
  • $1$ 枚目と $2$ 枚目のカードを選ぶ。
  • $1$ 枚目と $4$ 枚目のカードを選ぶ。
  • $1$ 枚目、$2$ 枚目および $3$ 枚目のカードを選ぶ。
  • $1$ 枚目、$3$ 枚目および $4$ 枚目のカードを選ぶ。

3 8
6 6 9

0

8 5
3 6 2 8 7 6 5 9

19

33 3
3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3

8589934591

• 答えは $32$ ビット整数型に収まらない場合があります。