정수 $N, X, Y, K$와 $M$이 주어집니다. 다음 조건을 모두 만족하는 길이 $N$인 정수 수열의 삼중쌍 $(A, B, C)$의 개수를 $M$으로 나눈 나머지를 구하세요.
- 각 $i = 1, 2, \dots, N$에 대하여, 튜플 $(A_i, B_i, C_i)$는 $(1, 2, 3)$의 순열입니다.
- 수열 $A$는 정확히 $X$개의 $1$과 $Y$개의 $2$를 포함합니다.
- $A$, $B$, $C$의 반전수(inversion의 개수)의 합은 $K$와 같습니다.
여기서 수열 $a$의 반전수란 $1 \le i < j \le |a|$와 $a_i > a_j$를 만족하는 정수 쌍 $(i, j)$의 개수로 정의됩니다.
입력
입력은 다음 형식으로 주어집니다:
N X Y K M
- 모든 입력값은 정수입니다.
- $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$.
출력
정답을 출력하세요.
예제 1
3 1 1 4 998244353
24
예제 2
4 0 0 18 123456789
0
예제 3
50 10 20 1000 1000000000
805988728
노트
첫 번째 예제에서는 조건을 만족하는 삼중쌍 $(A, B, C)$가 $24$개 있습니다. 예를 들어, $A = (1, 2, 3)$, $B = (3, 3, 2)$, $C = (2, 1, 1)$로 잡으면 $(A, B, C)$는 모든 조건을 만족합니다.