19401번 - Ascent Sequences 다국어

Consider a sequence $\langle a_1, a_2, \ldots, a_n \rangle$ of non-negative integers. An ascent in the sequence is a pair of adjacent elements such that the element with greater index has greater value. For example, there are two ascents in sequence $\langle 0, 2, 3, 1, 0 \rangle$: $a_1 = 0$ to $a_2 = 2$, and $a_2 = 2$ to $a_3 = 3$. Let us denote the number of ascents among the first $k$ elements of the sequence by $A_k$. In the given example, $A_1 = 0$, $A_2 = 1$, $A_3 = 2$, $A_4 = 2$ and $A_5 = 2$.

Sequence $a$ is called an ascent sequence if $a_1 = 0$ and for every $i \ge 2$ inequality $a_i \le A_{i-1} + 1$ is satisfied. For example, sequence $\langle 0, 2, 3, 1, 0 \rangle$ is not an ascent sequence because $a_2 = 2$ and $A_1 = 0$. Sequence $\langle 0, 1, 0, 2, 3 \rangle$ is, in turn, an ascent sequence because $A_1 = 0$, $A_2 = 1$, $A_3 = 1$, $A_4 = 2$.

Sequence $\langle a_1, a_2, \ldots, a_n \rangle$ of non-negative integers avoids pattern 201 if there are no $i$, $j$ and $k$ such that $i < j < k$ and $a_j < a_k < a_i$. For example, sequence $\langle 0, 1, 0, 2, 3 \rangle$ avoids pattern 201, while $\langle 0, 1, 2, 3, 1, 0, 2 \rangle$ does not avoid pattern 201 because for $i = 4$, $j = 6$, $k = 7$ we have $a_j = 0 < a_k = 2 < a_i = 3$.

You are given two integers $n$ and $p$. Find the number of ascent sequences of length $n$ avoiding pattern 201, and output this number modulo $p$.

The only line of the input contains two integers $n$ and $p$ ($1 \le n \le 500$; $2 \le p \le 10^9 + 123$; $p$ is a prime).

Output a single integer --- the number of ascent sequences of length $n$ avoiding pattern 201, modulo $p$.

In the first example test case, there are five ascent sequences of length 3 avoiding pattern 201: $\langle 0, 0, 0 \rangle$, $\langle 0, 0, 1 \rangle$, $\langle 0, 1, 0 \rangle$, $\langle 0, 1, 1 \rangle$, $\langle 0, 1, 2 \rangle$.

In the second example test case, there are 53 ascent sequences of length 5 and all of them except $\langle 0, 1, 2, 0, 1 \rangle$ avoid pattern 201.