小团是旅店老板，现在有连续的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