{"raw_statement":[{"iden":"problem statement","content":"Consider the following procedure of, given a string $X$ consisting of lowercase English alphabets, obtaining a new string:\n\n*   Split the string $X$ off at the positions where two different characters are adjacent to each other.\n*   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$.\n*   Concatenate the replaced strings without changing the order.\n\nFor 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` .\nFind 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$."},{"iden":"constraints","content":"*   $1 \\le N \\le 3000$\n*   $10^8 \\le P \\le 10^9$\n*   $N$ and $P$ are integers.\n*   $P$ is a prime."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$ $P$"},{"iden":"sample input 1","content":"3 998244353"},{"iden":"sample output 1","content":"26\n\nThose strings of which the $1$\\-st, $2$\\-nd, and $3$\\-rd characters are all the same satisfy the condition.\nFor example, `aaa` becomes `a3`, which satisfies the condition, while `abc` becomes `a1b1c1`, which does not."},{"iden":"sample input 2","content":"2 998244353"},{"iden":"sample output 2","content":"0\n\nNote 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."},{"iden":"sample input 3","content":"5 998244353"},{"iden":"sample output 3","content":"2626\n\nStrings like `aaabb` and `aaaaa` satisfy the condition."},{"iden":"sample input 4","content":"3000 924844033"},{"iden":"sample output 4","content":"607425699\n\nFind the number of strings satisfying the condition modulo $P$."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}