Counting Distinct Non‐decreasing Grid Fillings

Alice draws an n×m grid every day. Bob is required to fill each cell with an integer between 1 and k. Bob has learned to write the natural numbers from 1 to k. For each grid, Alice sets the following conditions:

• Each row must be filled with numbers in non‐decreasing order from column 1 to column m (i.e. if the row entries are \(a_1, a_2, \dots, a_m\) then \(a_1 \le a_2 \le \cdots \le a_m\)).
• Any two distinct rows must differ in at least one column (i.e. the rows must be pairwise distinct).
• The grid filling must be new (i.e. Bob must not repeat a grid that he has filled in any previous day).

If Bob fills the grid obeying these rules, Alice gives him one candy. Bob wonders what is the maximum number of candies he can collect if he fills a new grid every day.

Note: Since the answer can be very large, output it modulo \(p\).

Analysis: A valid grid is built by choosing an ordered sequence of n distinct rows, where each row is a non‐decreasing sequence of m numbers between 1 and k. The number of non‐decreasing sequences of length m with numbers in \([1,k]\) is given by the combinatorial formula \[ C(k+m-1, m)\ = \frac{(k+m-1)!}{m!(k-1)!}. \] Let \(X = C(k+m-1, m)\) be the number of possible rows. Since the rows in the grid must be pairwise distinct and order matters, the total number of valid grids equals \[ X \times (X-1) \times \cdots \times (X-n+1) = \prod_{i=0}^{n-1} (X - i). \] The answer is this product modulo \(p\). If \(n > X\) then the product is 0 as it is impossible to choose n distinct rows.

inputFormat

The input consists of a single line containing four space‐separated integers n, m, k, and p, where n and m specify the dimensions of the grid, k is the largest number Bob can write, and p is the modulus.

outputFormat

Output a single integer, the maximum number of candies Bob can collect (i.e. the total number of distinct valid grids), modulo p.

sample

2 2 2 997

6