测试数据来自 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秒。