Background

Under the star river, all is firefly dust,
I walk alone in the crowd while you wait, innocent.
If meeting is borrowing colors from paintings,
On Qingyuan, crimson sakura is like a sea.

— Yin Lin, "Qingyuan Sakura" (Cover: Renyi Daren).

Problem Description

Fusu really likes writing math problems while listening to ancient-style music, so this problem is actually an original question from Wusan.

Fusu wants to recreate the scenery of sakura blooming on Qingyuan, so he prepared many pairwise distinct sakura saplings and plans to plant them in a single row.

In this row, there are $n$ positions where sakura can be planted, and Fusu prepared $m$ saplings. Because sakura needs a lot of space on both sides when in full bloom, sakura cannot be planted next to each other. That is, between any two saplings, there must be at least one empty position where no flower is planted.

Planting in this way is not hard, but what Fusu is curious about is: how many valid plans are there to plant all $m$ saplings? A plan is valid if and only if it satisfies the requirement described in the previous paragraph. If we number the saplings as $1,2,3,\dots,m$, then two plans are different if and only if the chosen planting positions are different, or the sequence of sapling numbers from left to right is different.

To avoid overly large output, take the answer modulo a parameter $p$.

Input Format

Each input file contains exactly one set of testdata.

The testdata consists of one line with four integers, in order $type,~n,~m,~p$, where $type$ is a parameter that helps you determine the test point type, as described in the Constraints.

Output Format

Output one line containing one integer, which is the answer modulo $p$.

1 3 2 19260718

2

Hint

Explanation of Sample Input/Output 1

There are $2$ sakura saplings and $3$ planting positions. If the saplings are numbered $1,~2$ and the positions are numbered $1,~2,~3$, then the two plans are as follows:

Constraints and Agreements

This problem uses bundled testing with 6 subtasks in total.

Special Property 1: It is guaranteed that the actual number of plans for the corresponding test points (before taking modulo) does not exceed $10^6$.

Special Property 2: It is guaranteed that $p$ is a prime.

For $100\%$ of the data, it is guaranteed that:

• $1 \leq n \leq 2 \times 10^6$.
• $1 \leq m \leq 10^6$.
• $1 \leq p \leq 10^9$.
• $1 \leq m \leq \lceil\frac{n}{2} \rceil$.

Notes

• Please use appropriate data types for computations to avoid overflow.
• The parameter $type$ can help you quickly determine the subtask ID.

Translated by ChatGPT 5