背景

经典题目

描述

儿童节到了,你知道这天会有N个孩子来串门,但是你不知道他们谁是熊孩子谁不是熊孩子。或者说,你可以任意假定他们谁是熊孩子谁不是熊孩子。孩子只有熊孩子和非熊孩子之分。

现在这些孩子来了,由于实在太多了(详见数据范围),你需要把他们排成一队。顺序可以任意排列,但熊孩子之间如果相邻,会造成以下后果:

  • 发生可怕的事情
  • 你这道题会WA
  • ……(以下省略)

求所有可能的合法的方案总数。答案可能很大,只需输出它mod M的值。

注意如果一个排列倒过来看恰好是另一种排列,那么它们被视为同一种方案。例如(熊非熊非非)和(非非熊非熊)为同一种方案。

输入格式

两个整数N M

输出格式

一个整数,即答案。

样例输入

5 5555

样例输出

9

数据范围与约定

  • 对于10%的数据,
  • 对于20%的数据,
  • 对于30%的数据,
  • 对于40%的数据,
  • 对于60%的数据,
  • 对于100%的数据,

样例解释

9种方案分别为:非非非非非;

熊非非非非,非熊非非非,非非熊非非;

熊非熊非非,熊非非熊非,熊非非非熊,非熊非熊非;

熊非熊非熊。

来源

saffah做完某题之后送给saffah一样的弱菜的题

不得不说

人类的繁殖能力还真是可怕呢。