Counting Failure States in the Modified One‐Dimensional 2048 Game

In the modified one‐dimensional 2048 game, there is a row of n cells. At the start, one cell is filled with a block whose value is \(2\) (and we define its appearance time as \(1\)); all other cells are empty. In each move (numbered \(i\), starting from \(1\)), the player chooses a sliding direction (left or right) and the following steps occur:

1. All blocks slide to the chosen direction and are packed together (with no gaps).
2. After packing, as long as there exists an adjacent pair of blocks with the same value \(k\), they merge into one block with value \(2k\). This merge is performed in a way that (if the merged block is produced in the \(i\)th move) its appearance time is defined as \(2i\). Note that it can be proved that at no time will there be three consecutive blocks of equal value; hence the merge order is not ambiguous.
3. Finally, a new block with value \(2\) is generated at the cell at the end opposite to the sliding direction. This new block’s appearance time is \(2i+1\). However, if after step 2 all n cells are occupied (that is, no movement was possible), then no new block is generated and the game fails.

A win is achieved if at any moment a block with value \(2^x\) appears; when that happens the game terminates immediately with a win. In a failure state the board is full (all n cells contain blocks) and no block has reached the winning value \(2^x\).

We say that two failure states \(A\) and \(B\) are essentially equivalent if both of the following conditions hold:

• For every \(1 \le i \le n\), the block in cell \(i\) of state \(A\) has the same value as the block in cell \(i\) of state \(B\).
• For every pair of positions \(1 \le i < j \le n\), the relative order of the appearance times of the blocks in cells \(i\) and \(j\) is the same in both states.

Small Y is studying the number of essentially different failure states. It turns out that, if we observe the game closely, the final state obtained after a move (before attempting to add the new block) is uniquely determined by the number of blocks that have been generated overall. In fact, if we denote by \(m+1\) the total number of blocks generated (the initial block plus one new block per move), one may prove that the final state is exactly the result of processing \(m+1\) blocks with value \(2\) via the following procedure:

For each new block of value \(2\) (with its associated appearance time), append it to the right end of a list, then while the last two blocks in the list have the same value, remove them and append a block whose value is twice that value (with the current move’s merged appearance time).

A short analysis shows that the final state is completely determined by the integer \(L = m+1\); indeed, one may prove that the final state is essentially equivalent (in both the block values and the relative order of their appearance times) to the state corresponding to the binary representation of \(2L\) (note that since \(2L = L \ll 1\), the final state does not depend on the trailing zero).

The board is full (i.e. the game fails) exactly when the final state has exactly n blocks. Moreover, a win is prevented if every block has a value strictly less than \(2^x\). It can be shown that these conditions are equivalent to the existence of an integer \(L\) satisfying

[ \begin{cases} 1 \le L < 2^{x},\ popcount(L) = n, \end{cases} ]

where \(popcount(L)\) denotes the number of 1's in the binary representation of \(L\). Therefore, the number of essentially different failure states is exactly the number of integers \(L\) in the range \([1, 2^{x})\) with \(popcount(L) = n\); that is,

[ \text{Answer} = \binom{x}{n} \quad (\bmod; p). ]

Your task is to compute the number of essentially different failure states modulo a given integer p, given n, x and p.

inputFormat

The input consists of a single line with three positive integers n, x and p (\(1 \le n \le x\) and p is a positive integer; note that p is not necessarily prime).

outputFormat

Output a single integer: the number of essentially different failure states modulo p.

sample

1 4 1000

4

</p>