AT_kupc2024_k.Kyoto the Capital

给定整数 $N$ 和素数 $P$。

求满足下述条件的字符串 $S$ 的种数对 $P$ 取模的结果：

• $S$ 是一个长度为 $4N$ 的字符串，且恰好包含 $N$ 个字符 K，$N$ 个字符 Y，$N$ 个字符 O，$N$ 个字符 T。
• $S$ 包含连续子串 KYOTO。
• $S$ 不包含连续子串 TOKYO。

输入从标准输入读入，格式如下：

$N$ $P$

请输出答案。

部分分

对于满足下述条件的数据，答对可获得 1 分。

• $N \le 50$

样例解释 2

请输出答案对 $P$ 取模的结果。

数据范围

• 输入均为整数
• $1 \le N \le 500$
• $9 \times 10^8 \le P \le 10^9+7$
• $P$ 是素数

由 ChatGPT 5 翻译