Contest Duration: - (local time) (100 minutes) Back to Home
E - RLE /

Time Limit: 3 sec / Memory Limit: 1024 MB

問題文

• X を異なる文字が隣り合っている部分で分割する。
• 分割した各文字列 Y に対して、YY を構成する文字と Y の長さを繋げた文字列に置き換える。
• 元の順番を保ったまま、置き換えた文字列をすべて繋げる。

制約

• 1 \le N \le 3000
• 10^8 \le P \le 10^9
• N,P は整数
• P は素数

入力

N P


入力例 1

3 998244353


出力例 1

26


1,2,3 文字目が全て等しい文字列のみが条件を満たします。

入力例 2

2 998244353


出力例 2

0


aaa2 のように、長さが等しいものは条件を満たさないことに注意してください。

入力例 3

5 998244353


出力例 3

2626


aaabbaaaaa などが条件を満たします。

入力例 4

3000 924844033


出力例 4

607425699


Score : 500 points

Problem Statement

Consider the following procedure of, given a string X consisting of lowercase English alphabets, obtaining a new string:

• Split the string X off at the positions where two different characters are adjacent to each other.
• For each string Y that has been split off, replace Y with a string consisting of the character which Y consists of, followed by the length of Y.
• Concatenate the replaced strings without changing the order.

For example, aaabbcccc is divided into aaa,bb,cccc, which are replaced by a3,b2,c4, respectively, which in turn are concatenated without changing the order, resulting in a3b2c4.If the given string is aaaaaaaaaa , the new string is a10 .

Find the number, modulo P, of strings S of lengths N consisting of lowercase English alphabets, such that the length of T is smaller than that of S, where T is the string obtained by the procedure above against the string S.

Constraints

• 1 \le N \le 3000
• 10^8 \le P \le 10^9
• N and P are integers.
• P is a prime.

Input

Input is given from Standard Input in the following format:

N P


Output

Print the answer.

Sample Input 1

3 998244353


Sample Output 1

26


Those strings of which the 1-st, 2-nd, and 3-rd characters are all the same satisfy the condition.

For example, aaa becomes a3, which satisfies the condition, while abc becomes a1b1c1, which does not.

Sample Input 2

2 998244353


Sample Output 2

0


Note that if a string is transformed into another string of the same length, such as aa that becomes a2, it does not satisfy the condition.

Sample Input 3

5 998244353


Sample Output 3

2626


Strings like aaabb and aaaaa satisfy the condition.

Sample Input 4

3000 924844033


Sample Output 4

607425699


Find the number of strings satisfying the condition modulo P.