Description

给定数字序列$(A _1,A _2,…,A _n)$的子序列是任意序列$(A _{i 1},A _{i 2},…,A _{ik})$，其中$1≤i _1<i _ 2<i _k≤n$，若子序列是严格递增的，则称之为有序子序列。例如，序列$(1,7,3,5,9,4,8)$的有序子序列为$(1,7)、(3,4,8)$等。给定数字序列，求解其长度为$m$的有序子序列的个数。

Format

Input

输入包含多个测试用例，每个测试用例都包含两行。第$1$行包含两个整数$n（1≤n≤10000）$和$m（1≤m≤100）$，$n$表示序列的长度，$m$表示需要查找的有序子序列的长度；第$2$行包含序列的n个整数元素，每个元素的范围都为$0～987654321$。

Output

对每个测试用例，都输出答案“%$123456789$”。

Samples

3 2
1 1 2
7 3
1 7 3 5 9 4 8

2
12