Description

小 T 最近在学着买股票, 他得到内部消息: F 公司的股票将会疯涨. 股票每天的价格已知是 正整数, 并且由于客观上的原因, 最多只能为 \(n\). 在疯涨的 \(k\) 天中小 T 观察到: 除第一天 外每天的股价都比前一天高, 且高出的价格 (即当天的股价与前一天的股价之差) 不会超过 \(m\),\(m\) 为正整数. 并且这些参数满足 \(m(k - 1) \lt n\).

小 T 忘记了这 \(k\) 天每天的具体股价了, 他现在想知道这 \(k\) 天的股价有多少种可能.

Input

只有一行用空格隔开的四个数:\(n, k, m, p\). 对 \(p\) 的说明参见后面输出格式中对 \(p\) 的解释.

Output

仅包含一个数, 表示这 \(k\) 天的股价的可能种数对于 \(p\) 的模值.

Sample Input

7 3 2 997

Sample Output

16

Data Range

对于 20% 的数据, 满足:\(m, n, k, p \leq 20000\);

对于 100% 的数据, 满足:\(m, k, p \leq 10^9, n \leq 10^{18}\).

Explanation

神犇题解:http://www.cnblogs.com/jianglangcaijin/archive/2013/08/13/3254314.html

设相邻两项的差值为 \(a[i] = A[i+1] - A[i]\), 那么每一个这样的序列对答案的贡献为:

\[S = n - \sum_{i}^{k-1} a[i]\]

这样的序列 \(a\) 有 \(m^{k-1}\) 种, 则:

\[ans = \sum_{a[1]=1}^{m} \sum_{a[2]=1}^{m} \cdots \sum_{a[k-1]=1}^{m} (n - a[1] - a[2] - \ldots - a[k-1])\\ = n \cdot m^{k-1} - \sum_{a[1]=1}^{m} \sum_{a[2]=1}^{m} \cdots \sum_{a[k-1]=1}^{m} (a[1] + a[2] + \ldots + a[k-1])\\ = n \cdot m^{k-1} - \frac{m(m+1)}{2} \cdot m^{k-1} \cdot (k-1)\]

后面那一项是有 \(m^{k-1}\) 个数列, 每个数列有 \(k-1\) 个数, 则一共有 \(m^{k-1} \cdot (k-1)\) 个数,\(m\) 个数每个数均出现相等次数, 则每个数均出现 \(m^{k-2} \cdot (k-1)\) 次,\(m\) 个数的和为 $, 则总和为:

\[\frac{m(m+1)}{2} \cdot m^{k-1} \cdot (k-1)\]

照着 \(ans\) 推一遍结果基本就出来了.

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>

using namespace std;
typedef long long lli;
/* const */ lli modr = 1000000007;

lli qpow(lli a, lli b)
{
    lli res = 1;
    for (; b > 0; b >>= 1, a = a*a % modr)
        if (b & 1)
            res = res * a % modr;
    return res;
}

lli n, m, k;

int main(int argc, char** argv)
{
    scanf("%lld%lld%lld%lld", &n, &k, &m, &modr);
    lli res = n % modr * qpow(m, k-1) % modr
        - m * (m+1) / 2 % modr * qpow(m, k-2) % modr * (k-1) % modr;
    res = (res % modr + modr) % modr;
    printf("%lld\n", res);
    return 0;
}