小团是旅店老板，现在有连续的N个房间（从左到右分别编号从1到N），每个房间可以住一个旅客。
有P个游客通过美团酒店业务来到小团的旅店住宿，小团的任务是想办法给他们分配房间，要求相邻的两个房间不可以同时住上旅客。（比如3号房间和4号房间相邻，你可以两个房间都不住人，也可以3号房间住一个人4号不住，也可以3号不住4号房间住一个人，但不可以3号和4号都住人）
对于无法找到合法的方案进行分配的情况，输出0即可。
方案数不对具体的游客进行区分。例如1号房间住旅客A，3号房间住旅客B，和1号房间住旅客B，3号房间住旅客A视为同一种方案，即分配了1号和3号房间。
你的任务是给出有多少种分配的方案，方案数对10000取模即可。
保证 0 < P < N
一行两个以空格分开的自然数N和P。
对于40%的数据有2 <= N <= 10
对于60%的数据有2 <= N <= 100
对于100%的数据有2 <= N <= 1000
一行一个正整数表示分配的方案数量。
5 3
1
对于样例1，只有一种分配方案，分配1号房间、三号房间、五号房间，也即（1，3，5）
6 3
4
对于样例2，有四种分配方案，分别是（1，3，5），（1，3，6），（1，4，6），（2，4，6）
暂无题解
扫描二维码，关注牛客网
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
京公网安备
11010502036488号
