笨笨的车厢连接
背景
笨笨:哇…………………………
路人甲:这回又是干嘛了啊……
笨笨:呀…………………………
路人甲:偶不认识他……
笨笨:啊…………………………
路人甲:- -、
(旁白:过山车……)
描述
大家都知道,过山车可以有很多的车厢……
为了车子的安全(笨笨继续:啊……),要把重的车厢排在轻的车厢前面,并且用连接链连上,若是轻的车厢在重的车厢前面,则不需要连接链。
每辆过山车有n节车厢,车厢的重量有1~n,并且各不相同。
笨笨现在想知道,有n节车厢的车子有多少种方法使连接链数为k。
格式
输入格式
输入有多行,每行两个数n,k(0<=k<=n<=200)。
输出格式
对于每个询问输出一个方法数,由于结果可能很大,所以输出结果mod 2009后的数即可。
样例1
样例输入1
5 2
样例输出1
66
限制
1s
提示
不明白的看过来~~
假设有3节车厢,则它们的重量为1、2、3
当k=1时,3 1 2是一个符合的方法,2 1 3也是,1 3 2、2 3 1这4种都是符合的方法。
来源
笨笨原创。