#124. 小 H 排队 暂未评定

时间限制:1000 ms 内存限制:128 MiB 输入文件:queue.in 输出文件:queue.out
题目类型:传统 评测方式:文本比较
上传者: root

注意

本题采用文件输入输出。

输入文件为 queue.in, 输出文件为queue.out

题目描述

一年一度的展会要来临了,农民小 H 想要把 只奶牛和公牛安排在单独的一行中。
小 H 发现最近公牛们非常好斗;假如两只公牛在这一行中靠的太近,他们就会吵架,以至于斗殴,破坏这和谐的环境。小 H 非常的足智多谋,他计算出任何两只公牛之间至少要有 只奶牛,这样才能避免斗殴。
小 H 希望你帮助他计算一下有多少种安排方法,可避免任何斗殴的的发生。小 H 认为每头公牛都是一样的,每头奶牛都是一样的。因而,只要在一些相同的位置上有不同种类的牛,那这就算两种不同的方法。

输入格式

从文件 queue.in 中读入数据。

第一行:两个用空格隔开的数:

输出格式

输出到文件 queue.out 中。

一个单独的数,即小 H 可以安排的方法数。考虑到这个数可能很大,你只要输出 之后的结果就可以了。

样例

输入样例

queue.in

4 2

输出样例

queue.out

6

数据范围与提示

样例说明

小 H 想要一排 头牛,但是任何两只公牛之间至少有两头奶牛。下面的就是小 H 思考出可行的 种方案(C 代表奶牛,B 代表公牛)

CCCC
BCCC
CBCC
CCBC
CCCB
BCCB

数据范围

对于 的数据,
对于 的数据,