{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003ccenter\u003e \u003cimg class\u003d\"tex-graphics\" height\u003d\"151px\" src\u003d\"CDN_BASE_URL/571ac7be379a0813ed0f8820381feca9?v\u003d1726220399\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e \u003c/center\u003e\u003cp\u003e\u003cspan class\u003d\"tex-font-style-paragraph\"\u003e\u003c/span\u003e 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.\u003c/p\u003e\u003cp\u003eThe $$$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 \u0026gt; 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.\u003c/p\u003e\u003cp\u003eHowever, 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.\u003c/p\u003e\u003cp\u003eAiming 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.\u003c/p\u003e\u003cp\u003eWhat is the number $$$L$$$ that Mr. Pickles will obtain after counting all suitable trees?\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe input consists of a single line, with three space-separated integers: $$$R$$$, $$$N$$$, $$$M$$$, in that order.\u003c/p\u003e\u003cp\u003e\u003cspan class\u003d\"tex-font-style-paragraph\"\u003e\u003cspan class\u003d\"tex-font-style-bf\"\u003eLimits\u003c/span\u003e\u003c/span\u003e\u003c/p\u003e\u003cul\u003e \u003cli\u003e $$$1 \\leqslant R \\leqslant N \\leqslant 2021$$$ \u003c/li\u003e\u003cli\u003e $$$1 \\leqslant M \\leqslant 1\\,000\\,000\\,000$$$ \u003c/li\u003e\u003c/ul\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eThe output should contain a single line with the single integer $$$L$$$, which is the number of tree-like hierarchical structures that would match Mr. Pickles\u0027 constraints, counted modulo $$$M$$$.\u003c/p\u003e"}},{"title":"Examples","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2 4 2\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2 4 3\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003e\u003cspan class\u003d\"tex-font-style-paragraph\"\u003e\u003cspan class\u003d\"tex-font-style-bf\"\u003eSample Explanation 1\u003c/span\u003e\u003c/span\u003e\u003c/p\u003e\u003cp\u003eThe node with label $$$R \u003d 2$$$ is a leaf in exactly $$$3$$$ of five trees listed below, and thus there are $$$3$$$ trees that match Mr. Pickles\u0027 constraints. The only meaningful feature of our trees is parenthood, which represents mentorship relations, and thus there is no notion of \u003cspan class\u003d\"tex-font-style-underline\"\u003eleft child\u003c/span\u003e or \u003cspan class\u003d\"tex-font-style-underline\"\u003eright child\u003c/span\u003e of a node. Mr.\u0026nbsp;Pickles counts modulo $$$M \u003d 2$$$, and therefore he ends up with the number $$$L \u003d 3~(\\mathrm{mod~}2) \u003d 1$$$.\u003c/p\u003e\u003ccenter\u003e \u003cimg class\u003d\"tex-graphics\" height\u003d\"151px\" src\u003d\"CDN_BASE_URL/1a4c86ebad56e5923961b43c3e4d6565?v\u003d1726220399\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e \u003c/center\u003e\u003cp\u003e\u003cspan class\u003d\"tex-font-style-paragraph\"\u003e\u003cspan class\u003d\"tex-font-style-bf\"\u003eSample Explanation 2\u003c/span\u003e\u003c/span\u003e\u003c/p\u003e\u003cp\u003eMr. Pickles now counts modulo $$$M \u003d 3$$$, and thus he ends up with the number $$$L \u003d 3~(\\mathrm{mod~}3) \u003d 0$$$.\u003c/p\u003e"}}]}