{"problem":{"name":"RLE","description":{"content":"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","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":3000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc249_e"},"statements":[{"statement_type":"Markdown","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$.\n\n## Constraints\n\n*   $1 \\le N \\le 3000$\n*   $10^8 \\le P \\le 10^9$\n*   $N$ and $P$ are integers.\n*   $P$ is a prime.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $P$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc249_e","tags":[],"sample_group":[["3 998244353","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."],["2 998244353","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."],["5 998244353","2626\n\nStrings like `aaabb` and `aaaaa` satisfy the condition."],["3000 924844033","607425699\n\nFind the number of strings satisfying the condition modulo $P$."]],"created_at":"2026-03-03 11:01:13"}}