← 返回题目列表

AtCoder · arc221_b

B. 二次幂和

中文机器翻译题面 查看原题

分数: 800 点

问题陈述

给你一个正整数 N 和素数 P.

有一个长度-N 序列 A=(A_1,A_2,\ldots,A_N) 其中所有元素都是 0.

您可以重复以下操作任意次数,可能为零:

  • 选择一个非空子集 S of \lbrace 1,2,\ldots,N\rbrace。让 \displaystyle x=\sum_{i\in S}2^{i-1}。对于每个 i\in S,替换 A_i 与 x.

求模数 P,可能的序列 A 重复操作后。

约束

  • 1\leq N\leq 700
  • P 是一个令人满意的素数 10^8\lt P\lt 10^9.
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N P

输出

输出答案。


示例输入 1

1 998244353

示例输出 1

2

可能的序列 A 是 (0),(1),给出两种可能性。


示例输入 2

2 998244353

示例输出 2

7

可能的序列 A 是 (0,0),(0,2),(1,0),(1,2),(1,3),(3,2),(3,3),给出了七种可能性。


示例输入 3

3 998244353

示例输出 3

57

示例输入 4

4 998244353

示例输出 4

1208

示例输入 5

77 777777773

示例输出 5

381787647