SP2734 LARGE - Large party

有一个客人非常多的宴会，主办方买好了一张巨大的圆桌（而且只有一张），于是便开始思考如何分配座位。考虑到如果有超过k名女士坐在一起，那么她们将彻夜闲聊，而不会和其他任何人说一句话。为了避免这种情况的发生，营造一个祥和的气氛，该如何分配这些座位呢？有几种方法分配呢？ 注：客人的性别不确定，本题的题意是在总数一定、女士分配规则一定的情况下，共有多少种性别排列方式。

无

对于每一组输入，输出一个整数ans，表示总共的性别分配方式。结果可能很大，你需要输出对100000007取余后的结果。 样例解释 以下M表示男士，W表示女士。 在第一组数据中，共有两种性别分配可能：MMM或MMW。 在第二组数据中，共有四种性别分配可能：MMM，MMW，MWW，WWW。 在第三组数据中，共有三种性别分配可能：MMMM，MMMW，MWMW。 圆桌足够大，同时保证1