問題文

整数 N と素数 P が与えられます。

K, Y, O, T の文字を N 個ずつ含む長さ 4N の文字列 S であって、 KYOTO を（連続する）部分文字列に含み TOKYO を（連続する）部分文字列に含まないものの個数を P で割った余りを求めてください。

制約

• 入力は全て整数
• 1 \le N \le 500
• 9 \times 10^8 \le P \le 10^9+7
• P は素数

部分点

以下の制約を満たすデータセットに正解した場合は 1 点が与えられる。

• N \le 50

入力例 1

2 998244353

出力例 1

24

入力例 2

10 1000000007

出力例 2

93856993

答えを P で割った余りを出力してください。