小Q给你n个数1,2,3...n，代表n个楼，第i个楼的高度为i，每个楼都有一个颜色
现在将这些楼随机排列在一条直线上，问有多少种排列方式，满足从最左边往右看（站在左边很远的地方看）能看到L-1次颜色的变变化，答案对le9+9取模
如果两个相同颜色楼的高度分别为H1，H2（H1<H2），H1在左边，且H1 H2之间的楼都比H1矮，那么站在左边来看就是一种颜色
你能看到一个楼的前提是这个楼之前的楼都比它矮
第一行输入两个整数n，L（1<=n<=1296），（1<=L<=n）
第二行输入n个整数Ci表示每个楼的颜色（1<=Ci<=n）
保证30%数据(n<=10,L<=10)
保证70%数据(n<=500,L<=500)
保证100%的数据(n<=1296,L<=1296)
输出一个整数，代表方案数，并对le9+9取模
4 3 1 1 2 1
6