该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Background

世界是一张连通图。 你在这里，ta在那里。

Description

具体地，世界是一张连通的无向图，包含 $n$ 座城市，标号 $1,2,\cdots,n$。任意两座不同的城市之间可能存在一条双向通路，也可能不存在。这个世界很大，为了来到一座邻近的城市，人们需要付出一整天的代价。

你生活在城市 $1$，但ta却生活在城市 $n$，触不可及……

你想知道，从城市 $1$ 启程后，至少多少昼夜才能抵达城市 $n$。彼时的你从未离开这座城市，也无从知晓这个世界的道路分布。不过，估算从城市 $1$ 到城市 $n$ 的最短路一定难不倒你。请你求出，对于所有可能的道路分布，从城市 $1$ 到城市 $n$ 的最短路长度之和。答案对大质数 $p$ 取模。

Format

Input

输入共一行，包含两个整数 $n,p$，表示图的点数与模数。

Output

输出共一行一个整数，表示答案对 $p$ 取模后的值。

Samples

 3 1001177

5

6 1000253

41880

42 100002593

44678783

Limitation

对于全部测试数据，满足 $2 \le n \le 400, 10^6 \le p \le 10^9+9$。