Universal Cup Judging System

Universal Cup

حد الوقت: 3.0 s حد الذاكرة: 1024 MB مجموع النقاط: 100 قابلة للهجوم ✓
الإحصائيات

You are given integers $N, X, Y, K$, and $M$. Find the number of triples $(A, B, C)$ of integer sequences of length $N$ that satisfy all of the following conditions, modulo $M$.

  • For each $i = 1, 2, \dots, N$, the tuple $(A_i, B_i, C_i)$ is a permutation of $(1, 2, 3)$.
  • The sequence $A$ contains exactly $X$ occurrences of $1$ and $Y$ occurrences of $2$.
  • The sum of the number of inversions of $A$, $B$, and $C$ is equal to $K$.

Here, the number of inversions of a sequence $a$ is defined as the number of pairs of integers $(i, j)$ satisfying $1 \le i < j \le |a|$ and $a_i > a_j$.

Input

The input is given in the following format:

N X Y K M
  • All input values are integers.
  • $2 \le N \le 50$.
  • $0 \le X, Y \le N$.
  • $X + Y \le N$.
  • $0 \le K \le \frac{3}{2}N(N - 1)$.
  • $10^8 \le M \le 10^9$.

Output

Print the answer.

Sample 1

3 1 1 4 998244353
24

Sample 2

4 0 0 18 123456789
0

Sample 3

50 10 20 1000 1000000000
805988728

Note

In the first example, there are $24$ triples $(A, B, C)$ that satisfy the conditions. For example, if we take $A = (1, 2, 3)$, $B = (3, 3, 2)$, and $C = (2, 1, 1)$, then $(A, B, C)$ satisfies all the conditions.

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.