← 返回题目列表

AtCoder · abc281_g

G. 最远的城市

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

分数: 600 点

问题陈述

给你正整数 N 和 M.
求模数 M,简单连通无向图 N 顶点编号 1, \dots, N 满足以下条件。

  • 对于每个 u = 2, \dots, N-1,距顶点的最短距离 1 到顶点 u 严格小于距顶点的最短距离 1 到顶点 N.

这里,距顶点的最短距离 u 到顶点 v 是连接顶点的简单路径中的最小边数 u 和 v.
当且仅当有两个顶点时,两个图被认为是不同的 u 和 v 由其中一个图中的边连接。

约束

  • 3 \leq N \leq 500
  • 10^8 \leq M \leq 10^9
  • N 和 M 是整数。

输入

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

N M

输出

打印答案。


示例输入 1

4 1000000000

示例输出 1

8

以下八张图满足条件。

example_00


示例输入 2

3 100000000

示例输出 2

1

示例输入 3

500 987654321

示例输出 3

610860515

一定要找到模数 M.