eolymp
bolt
Try our new interface for solving problems
Problems

Mentors

Mentors

The Happy Tree Friends have gathered for their annual meeting, in which they take their most important decisions for the year to come. This year, they will set up a mentoring program to help each other take better care of their loved ones. This programme follows a tree-like hierarchical structure as follows. The $n$ members of the programme are ranked from $1$ to $n$ (each rank is assigned once), by increasing seniority. For the mentorship programme to be efficient, a person ranked $a$ can mentor a person ranked $b$ only if $a > b$. The most senior Happy Tree Friend can have no mentor, but everybody else has a unique mentor. Conversely, everybody is allowed to mentor from zero to two people. However, Mr. Pickles, who was assigned the rank $r$, plans to take a sabbatical this year. Thus, he will not be able to mentor anybody, and the Happy Tree Friends should choose their hierarchical structure among those trees in which the node labelled $r$ is a leaf. Aiming to help his friends to choose such a tree, Mr. Pickles decides to first count how many trees would match his constraint. Unfortunately, he stopped school early, and thus did not learn how to manipulate integers of arbitrary size. Instead, he counts modulo $m$, where $m$ is a fixed positive integer: this is already enough for most purposes in life. What is the number $l$ that Mr. Pickles will obtain after counting all suitable trees? \InputFile Contains three integers $r, n~(1 \le r \le n \le 2021)$ and $m~(1 \le m \le 10^9)$. \OutputFile Print a single integer $l$, which is the number of tree-like hierarchical structures that would match Mr. Pickles' constraints, counted modulo $m$. \Examples Explanation 1. The node with label $r = 2$ is a leaf in exactly $3$ of five trees listed below, and thus there are $3$ trees that match Mr. Pickles’ constraints. The only meaningful feature of our trees is parenthood, which represents mentorship relations, and thus there is no notion of left child or right child of a node. Mr. Pickles counts modulo $m = 2$, and therefore he ends up with the number $l = 3~(mod~2) = 1$. \includegraphics{https://static.eolymp.com/content/es/eslmdn5t4p19hafa12lkmsfjvg.gif} Explanation 2. Mr. Pickles now counts modulo $m = 3$, and thus he ends up with the number $l = 3~(mod~3) = 0$.
Time limit 1 second
Memory limit 128 MiB
Input example #1
2 4 2
Output example #1
1
Input example #2
2 4 3
Output example #2
0
Source 2021 ACM Southwestern Europe Regional Contest (SWERC), Paris, March 7, Problem F