Public Judge

pjudge

Time Limit: 1 s Memory Limit: 512 MB Total points: 100

# 21741. 【NOIP Round #5】青鱼和区间

统计

由于 UOJ 也缺头,且下一题的造题 AI 效果不尽如意,鱼王青鱼重新训练了一个 AI。

题目描述

鱼王青鱼的 AI 不愿意进行 996 的工作,于是要求青鱼先和它玩一个游戏。

AI 生成了 $n$ 道题,编号为 $1, 2, \dots, n$。现在 AI 心里选择了其中一道题,但青鱼不知道这是哪一题。

青鱼可以向 AI 询问若干个问题,每个问题形如:给定 $l, r$ 满足 $1 \le l \le r \le n$,询问这道题的编号是否在 $[l, r]$ 中。

如果青鱼能够通过同时询问这些问题唯一确定这道题的编号,那么青鱼就赢了。否则 AI 就赢了。

显然,身为鱼王,青鱼的智商不输 AI。因此,你可以认为青鱼和 AI 都是绝顶聪明的。

现在青鱼抓住了你,并要求你计算出青鱼有多少种问问题的方案使得他一定能赢。其中两种方案不同,当且仅当存在一个区间 $[l, r]$ 在其中一种方案中被询问,而在另一种方案中没有。

另外,青鱼施行仁政,所以他不会太为难你,只需要你给出答案对大质数 $P$ 取模的结果。

输入格式

第一行,两个正整数,$n, P$, 含义同题目描述。

输出格式

一行,一个非负整数,表示答案对大质数 $P$ 取模的结果。

样例数据

样例 1 输入

3 998244353

样例 1 输出

48

样例 2 输入

7 999997543

样例 2 输出

256097184

样例 3 输入

100 1000000007

样例 3 输出

402821964

数据范围

本题共有 $10$ 个测试点,各测试点等分。

对于第 $1 \sim 2$ 个测试点,$n \le 6$。

对于第 $3 \sim 4$ 个测试点,$n \le 20$。

对于第 $5 \sim 6$ 个测试点,$n \le 80$。

对于所有测试点,$1 \le n \le 300$,$10^8 \le P \le 10^9+7$。