楼房

题号：NC21617
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

给你n个数1 2 3。。n，代表n个楼，第i个楼的高度为i，每个楼会有一种颜色

现在问有多少的排列满足从左往右（站在左边很远的地方看）看能看到L种颜色（即看到了L-1次颜色的变化）,答案对1e9+9取模

如果两个相同颜色楼的高度分别为H1,H2 (H1 < H2), H1在左边，且H1 H2之间的楼都比H1矮，那么站在左边来看就是一种颜色

你能看到一个楼的前提是这个楼之前的楼都比它矮

第一行输入两个整数n，L(1 ≤ n ≤ 1296) ， (1 ≤ L ≤ n)

第二行输入 n个整数c_i表示每个楼的颜色  (1 ≤ c_i ≤ n)

输出一个整数

示例1

复制

4 3
1 1 2 1

复制

1, 2, 3, 4 （1,2同色，看上去就是一种颜色，因此这个排列只能看到3种颜色）

1, 3, 2, 4

1, 3, 4, 2

2, 1, 3, 4

2, 3, 1, 4

2, 3, 4, 1

示例2

复制

8 5
1 2 2 3 3 3 1 4

复制

子任务一30分：n<=50

子任务二30分：n<=200

子任务三40分：n<=1296