题目描述
A校和B校互为友好学校, 两校教师之间、学生之间常有一些互访交流和联欢活动。今B校的m名学生来到A校, 要与A校的n名学生开一个联欢晚会。会场周围从1号座位到m+n号座位几乎排了一圈, 只是入口的大门把1号座位和m+n号座位隔开了。也就是说, 除了1号和m+n号座位外, i(1<i<m+n)号座位与i-1号和i+1号座位是相连的。
为增加交流和接触, B校校方希望本校学生坐的不要过于集中, 为此特作出对B校学生的限制性规定: 不允许k名B校学生座位相连。当然, B校校方不便要求A校学生如何坐。请编程求出满足B校规定的所有做法共有多少种?
这里所说的坐法对同校学生不加区别。例如当n=3、m=3、k=3时
BBABAA BBAABA BBAAAB BABBAA
BABABA BABAAB BAABBA BAABAB
BAAABB ABBABA ABBAAB ABABBA
ABABAB ABAABB AABBAB AABABB
符合B校规定的坐法共有这16种。
输入
输入文件名为party.in, 其中的数据依次为n、m、k, 用空格做间隔符。
对于50%的数据, n、m、k均不大于10
对于100%的数据, n、m、k均不大于100
输出
输出文件名为party.out, 只包含一个整数, 即符合B校规定的坐法总数。
样例输入输出
提示