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