H-代码蛋糕 (ᗜˬᗜ)_牛客2025年1024程序员节娱乐赛

时间限制：C/C++/Rust/Pascal 9秒，其他语言18秒
空间限制：C/C++/Rust/Pascal 999 M，其他语言1998 M
64bit IO Format: %lld

题目描述

在 $10$ 月 $24$ 日的 $1024$ 程序员节这天，琪露诺准备了 $n$ 块“代码蛋糕”，按编号 $\{1,2,\dots,n\}$ 排列。你可以从中选出一个非空子集，并按某种顺序吃掉，要求:

特殊地，编号 $1$ 既不是质数也不是合数，可以与任意编号相邻。请你计算满足上述要求的合法吃法总数。由于答案可能很大，请将答案取模后输出。

【质数】若整数 $x > 1$ 的正因数只有 $1$ 和 $x$ 本身，则称为质数。
【合数】若整数 $x > 1$ 存在除 $1$ 与 $x$ 之外的正因数，则称为合数。

每个测试文件均包含多组测试数据。第一行输入两个整数，分别为数据组数  和模数 ，每组测试数据描述如下：
第一行输入一个整数  代表“代码蛋糕”的数量。

对于每一组测试数据，共  行，每一行输出一个整数，代表答案。由于答案可能很大，请将答案对模数  取模后输出。

示例1

复制

3 999999999
9
99
999

复制

0
34893099
484205818

2 1 3 和 3 1 2 这样的吃法是合理的，是质数、非质数、质数的方案，不视为是连续吃质数编号的蛋糕。

真吃得完这么多蛋糕吗？