問題文

今、冷蔵庫には、$N$個の整数$A_i(1 \leq i \leq N)$が入っています。お腹が空いてしまったかんてん君は、大好物の整数を食べることにしました。
そのままでは食べることができないので、かんてん君は、$K$個以上の整数を選んで、次の操作のどちらかを1回のみ行い、できた整数を食べます。
・加熱調理　－　選んだ整数を全て混ぜて、加熱します。できる整数は、選んだ整数の総和です。
・加圧調理　－　選んだ整数を全て圧力器の中に入れ、加圧します。できる整数は、選んだ整数の総積です。
調理方法がこの２つしか存在しないとすると、かんてん君が食べることのできる整数は何種類あるでしょう？

入力

$N\ K$
$A_1\ A_2\ \cdots\ A_N$

すべてのテストケースは、次の制約を満たします。
・$2 \leq N \leq 18$
・$2 \leq K \leq N$
・$1 \leq A_i \leq 10^3(1 \leq i \leq N)$
・入力は全て整数

出力

かんてん君が食べることのできる整数の種類数を1行に出力してください。また、最後に改行してください。

サンプル

4 2
1 2 3 5

12

2 2
2 2

1