問題文

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

入力

$NK$
$A_1{A}_2\cdots A_N$

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

出力

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

サンプル

4 2
1 2 3 5

12

2 2
2 2

1