题面

在 SMZX,英俊潇洒、风流倜傥、一表人才、玉树临风、气宇轩昂、温文尔雅、风度翩翩的 lah，有\(n\)个粉丝。现在他举办了一场见面会，他要把\(n\)个人分成若干个组，组数没有限制，这些组需要满足一些条件。现在假设 lah 将粉丝分成了\(k\)个组，其中第\(i\)组的人数为\(s_i\),那么限制条件如下：

1. \(∀1 < i ≤ k, s_i ≥ s_{i-1}\)
2. \(x ≤ s_1 ≤ y\)
3. \(\sum_{i=1}^{k} s_i = n\)

其中\(x,y\)是两个给定的整数。
现在他想知道分组的方案数，答案对一个整数\(P\)取模（\(P\)不一定是质数）

输入格式

一行，四个整数：\(x,y,n,P\)，含义如题面所示。

输出格式

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

样例

Input 1

2 4 7 998244353

Output 1

3

数据规模

对于20%的数据，满足\(n ≤ 100\);
对于40%的数据，满足\(n ≤ 2 × 10^3\);
对于另外10%的数据，满足\(P = 998244353\)
对于另外10%的数据，满足\(x = 1, y = n\);
对于100%的数据，满足\(1 ≤ x ≤ y ≤ n ≤ 1 × 10^5, 1 ≤ P ≤ 10^9 + 7\) 。