KIS

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

长度为 n 的一个序列,保证每个数都互不相同,问长度为 k 的上升子序列有多少个。

注:子序列是找出一个序列的一部分,不要求连续,比如 abcde 的序列,cde 和 ace 都是它的子序列。

Input

输入数据有多组(数据组数不超过 100),到 EOF 结束。

对于每组数据:

  • 第一行输入一个 n (0 < n <= 100)
  • 第二行输入 n 个整数 a[i] (0 < a[i] <= 1e9)
  • 第三行输入一个整数 k (0 < k <= n)

Output

对于每组数据,输出一行,表示长度为 k 的上升子序列有多少个,由于答案可能很大,你需要把答案对 1000000007 取模。

Sample Input

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

Sample Output

6
196

Hint

Source

【2016级《程序设计基础(B)II》期末上机考试-第二场】Johsnows