For a sequence $ a $ of length $ n $, define $ f(a)=\dfrac{1}{\prod\limits_{i=k}^ns_i} $, where $ s_i $ is the prefix sum array of $ \{a_n\} $, and $ k $ is a given constant such that $ 1\le k\le 2 $.

Consider all sequences $ a $ that satisfy the following three conditions:

• The length of $ a $ is $ n $.
• $ \forall i,j $, $ a_i\ne a_j $.
• $ 1\le a_i\le m $.

Calculate the sum of $ f(a) $ for all such sequences, modulo $ p $. It is guaranteed that $ p $ is a prime number.

Input

The first line contains four integers $ n, m, k, p $, representing the sequence length, the upper bound of the sequence elements, and the modulus, respectively.

Output

Output a single integer representing the answer modulo $ p $.

Examples

Input 1

2 3 2 1000000007

Output 1

966666675

Input 2

3 5 2 998244353

Output 2

148276980

Input 3

6 10 2 1004535809

Output 3

622165218

Input 4

30 40 1 265371653

Output 4

179937201

Constraints

For all test cases, it is guaranteed that $ 2\le n\le m\le 100 $, $ 10^8 < p < 1.07\times 10^9 $, $ p $ is a prime number, and $ 1\le k\le 2 $.

• Subtask 1 (10 pts): $ m\le 20 $.
• Subtask 2 (25 pts): $ k=1 $.
• Subtask 3 (15 pts): $ n=m\le 30 $.
• Subtask 4 (10 pts): $ m\le 30 $.
• Subtask 5 (15 pts): $ m\le 40 $.
• Subtask 6 (10 pts): $ m\le 70 $.
• Subtask 7 (15 pts): $ m\le 100 $.