粉丝

题面

在 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\) 。

信息

ID
1080
难度
10
分类
(无)
标签
(无)
递交数
1
已通过
0
通过率
0%
上传者