题意描述

小诗想要你帮她做线代作业，但是向量空间是九级知识点，你还没有掌握，于是她换了道作业题给你做。

对于所有长度为 $n$ 的 01 串 $s$ （下标从 $1$ 开始），定义 $f(s)=\sum_i[s_i=0][s_{i+1}=1]i$ （ $[x]$ 表示 $x$ 为真），令 $T$ 表示所有 $n$ 个 $0$ ， $m$ 个 $1$ 的零一串集合，她想知道：

保证 $p,q$ 是素数。

输入格式

一行四个正整数 $n,m,p,q$ 。

输出格式

一行一个非负整数，表示答案。

样例

样例输入 #1

1 2 2 2

样例输出 #1

1

样例解释 #1

$T=\{011,101,110\}$ ，对应的 $f(s)$ 值分别为 $1,2,0$ ，答案为 $(2^1+2^2+2^0)\bmod 2=1$ 。

样例输入 #2

2 2 1444441 41

样例输出 #2

9204

样例解释 #2

$T=\{0011,0101,0110,1001,1010,1100\}$ ，对应的 $f(s)$ 值分别为 $2,4,1,3,2,0$ ，答案为 $(41^2+41^4+41^1+41^3+41^2+41^0)\bmod 1444441=9204$ 。

样例 3~5 见下发文件。

数据范围

对于所有测试点，保证 $1\leqslant n,m,q\leqslant 10^9,2\leqslant p\leqslant 10^7$ ，且 $p,q$ 为素数。

请注意，本题有子任务捆绑。