ICPC NAC 的工作人员编写了一些题目，并希望从中构建一套题目。每道题目都有一个正整数难度分值。

如果一个竞赛中题目的难度分值按升序排列后，从第三道题开始，每一道题的难度分值都小于或等于其前两道题难度分值之和，那么该竞赛就具有“Nice”难度分布。

给定一组题目的难度分值以及希望组成的题目数量，计算有多少种具有“Nice”难度分布的题目组合。如果两个题目组合中存在一道题目属于其中一个组合但不属于另一个，则认为这两个题目组合是不同的。（特别注意，即使题目顺序不同，两个题目组合也被视为相同。）

输入格式

输入的第一行包含两个整数 $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