测试数据来自 system/2035

描述

Q先生是一个热爱学习的男孩子。

他认为一个 $n$ 位的正整数 $x$ 若能被称作是绚丽多彩的，一定要满足对于 $\{1,3,5,7,9\}$ 中任意一个奇数或者没有在 $x$ 中出现，或者在 $x$ 中出现了恰好奇数次；同时对于 $\{0,2,4,6,8\}$ 中任意的偶数或者没有在 $x$ 中出现，或者在 $x$ 中出现了偶数次。同时需要注意 $x$ 是不能有前导零的。

例如 $141221242$ 就是一个九位的绚丽多彩的数。

现在Q先生给定了正整数 $n$ 与另外一个正整数 $p$，希望你统计出来一共有多少不超过 $n$ 位的绚丽多彩的数，并输出模 $p$ 后的余数。

格式

输入格式

输入有一行，包含两个由空格隔开的正整数，分别为 $n$ 和 $q$。

输出格式

输出一个正整数，表示不超过 $n$ 位的绚丽多彩数的总数模 $p$ 后的余数。

样例1

样例输入1

7 1000000123

样例输出1

287975

样例2

样例输入2

100 1000000123

样例输出2

123864868

限制

对于前 $40\%$ 的数据，满足 $n$ 一定是 $2$ 的幂。

对于 $100\%$ 的数据，满足 $2\le n\le 2^{60}$ 且 $10^9 \le p \le 2\times 10^9$。

每一组数据时限为2秒。