ICPC NACのスタッフは、いくつかの問題を作成し、それらから問題セットを構築したいと考えている。各問題には正の難易度評価が付けられている。

コンテストの問題セットが「Nice」な難易度分布を持つとは、問題の難易度を昇順に並べたとき、3番目以降のすべての問題の難易度が、その直前の2つの問題の難易度の和以下であることを指す。

与えられた問題セットの難易度と、セットに必要な問題数に対して、「Nice」な難易度分布を持つ問題セットの数を数えよ。2つの問題セットは、一方には含まれるがもう一方には含まれない問題が存在する場合にのみ異なるとみなす。（具体的には、問題の順序が入れ替わっていても、含まれる問題が同じであればその2つの問題セットは同一であることに注意せよ。）

入力

入力の最初の行には、2つの整数 $n$ ($3 \le n \le 50$) と $k$ ($3 \le k \le 18, k \le n$) が含まれる。ここで $n$ は審査員が作成した問題の数であり、$k$ は問題セットに入れたい問題の数である。

続く $n$ 行の各行には、単一の整数 $d$ ($1 \le d \le 10^9$) が含まれる。これらは問題の難易度である。

出力

「Nice」な難易度分布を持つ問題セットの可能な組み合わせの数を、単一の整数として出力せよ。

入出力例

入力 1

5 4
2
1
4
3
5

出力 1

4

入力 2

8 5
1
2
3
5
8
13
21
34

出力 2

4