問題文

$2$ 以上の整数 $n$ と正整数 $m$ が与えられます。

次の $2$ つの条件を同時に満たす平面上の点 $(x,y)$ を 良い点 と呼びます。

• $x,y$ はどちらも正整数である
• $x+y$ は $2n$ 以下の 偶数 である

良い点は有限個なので、その個数を $k$ とします。また良い点全体の集合を $V = \lbrace (x_1,y_1),(x_2,y_2),\ldots,(x_k,y_k)\rbrace$ とし、さらに $v_i\coloneqq(x_i,y_i)$ とします。 特に $(1,1)$ は必ず良い点であり、$v_1=(1,1)$ とします。

$V$ を頂点集合とする単純無向グラフ $G$ を次のように構成します。

• 全ての $1\leq i,j\leq k$ なる整数 $i,j$ について、$\lvert x_i-x_j\rvert + \lvert y_i-y_j\rvert = 2$ のとき、またそのときに限り $v_i$ と $v_j$ を結ぶ辺が存在する

次の $2$ つの条件を同時に満たす $G$ の全域木 $T$ を 良い全域木 と呼びます。

• 全ての $i=1,2,\ldots,k$ について、$T$ に含まれる辺を $\dfrac{x_i+y_i}{2}-1$ 回だけ辿ることで頂点 $v_1$ から頂点 $v_i$ に到達できる
• 頂点 $v_i,v_j$ ($i\neq j$) を端点とする線分を $L_{i,j}$ とする。$T$ に含まれる任意の相異なる $2$ 辺 $\lbrace v_a,v_b\rbrace,\lbrace v_c,v_d\rbrace$ について、$L_{a,b}$ と $L_{c,d}$ は端点以外で共有点を持たない

良い全域木 $T$ に対して、$T$ に含まれる次数 $1$ の頂点の $x$ 座標の積を $f(T)$ とします。

全ての良い全域木 $T$ に対する $f(T)$ の総和を $m$ で割ったあまりを求めてください。

入力

入力は以下の形式で標準入力から与えられる。

$n$ $m$

• 入力は全て整数で与えられる
• $2\leq n\leq 5\times 10 ^ 6$
• $1\leq m\leq 10 ^ 9$

出力

全ての良い全域木 $T$ に対する $f(T)$ の総和を $m$ で割ったあまりを $1$ 行に出力して改行してください。

サンプル

サンプル1

入力サンプルをコピー

入力

2 12

出力

6

$n=2$ に対するグラフ $G$ を下図左側に示します。

この $G$ に対して良い全域木は図の右側に示したもの唯一つです。図の読み方ですが、赤の実線で描いた辺を全域木に含む辺としています。

この全域木において次数が $1$ の頂点は黒く塗った $(1,3),(2,2),(3,1)$ の $3$ つであり、その $x$ 座標はそれぞれ $1,2,3$ です。つまりこの全域木 $T$ に対する $f(T)$ は $1\cdot 2\cdot 3 = 6$ となり、このケースに対する答えは $6$ です。

サンプル2

入力サンプルをコピー

入力

3 31415

出力

1200

$n=3$ に対するグラフ $G$ を下図左側に示します。

この $G$ に対する良い全域木の一例を図の右側に示します。この全域木 $T$ において次数が $1$ の頂点は $(1,5),(2,2),(2,4),(3,3),(4,2),(5,1)$ の $6$ つなので、$f(T) = 1\cdot 2 ^ 2 \cdot 3 \cdot 4\cdot 5 = 240$ となります。

なお、下図に示すような全域木はよい全域木ではないことに注意してください。

4 1

0

436279 998244353

227931850