一个合法括号序列可以递归地定义如下：

• 空串是一个合法括号序列。
• 如果 $X$ 和 $Y$ 是合法括号序列，那么 $XY$（$X$ 和 $Y$ 的拼接）也是一个合法括号序列。
• 如果 $X$ 是一个合法括号序列，那么 $(X)$ 也是一个合法括号序列。

每个合法括号序列都可以通过上述规则推导出来。

对于一个括号序列，你可以对其进行以下操作：

• 每次你可以选择两个下标 $L$ 和 $R$，满足 $L \le R$。该操作会修改从 $L$ 到 $R$（包含端点）的字符。
• 首先，将这些字符的顺序翻转。
• 然后，将每个字符变换为其相反的字符。也就是说，指定范围内的每个 ( 变为 )，反之亦然。

一个括号序列的值定义为将其转换为合法括号序列所需的最少操作次数。如果无法转换，则该序列的值为 $10^{100}$。

例如，“()((” 的值为 $1$，“()()” 的值为 $0$，“(((” 的值为 $10^{100}$。

给你一个整数 $n$。对于每个 $1 \le i \le n$，求长度为 $n$ 且值为 $i$ 的不同括号序列的数量 $A_i$，然后计算总和 $\sum_{i=0}^{n} ((i + 1) \cdot A_i)$（其中 $A_0$ 为长度为 $n$ 且值为 $0$ 的不同括号序列的数量）。

由于答案可能非常大，请将其对给定的整数 $m$ 取模后输出。

输入格式

输入的第一行包含两个整数 $n$ 和 $m$（$1 \le n \le 10^6$，$1 \le m \le 10^9$）。

输出格式

输出一个整数：表示问题的答案。

样例

输入样例 1

1 100

输出样例 1

0

输入样例 2

10 100

输出样例 2

68