3. 数列求和

【题目背景】

Kyouko 是数学天才的说是，闲着没事不知道在哪里整个数列求和的题给你。

【题目描述】

给定 $n,a,k,P$，求出：
$$\left(\sum_{i=1}^n i^ka^i\right)\bmod P$$大洋里

【输入格式】

一行四个整数，分别是 $n,a,k,P$。

【输出格式】

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

【样例输入1】

3 4 0 1000000007

【样例输出1】

84

【样例输入2】

3 10 1 1000000007

【样例输出2】

3210

【样例输入3】

3 9 2 1000000007

【样例输出3】

6894

【数据规模与约定】

本题共 $10$ 个测试点。

对于测试点 $1\sim 2$，有特殊性质满足 $n\le 10^6$。

对于测试点 $3\sim 4$，有特殊性质满足 $k=0$。

对于测试点 $5\sim 6$，有特殊性质满足 $a=1$，其中两个测试点分别满足 $k\le100/k\le 2000$。

对于测试点 $7\sim 8$，有特殊性质满足 $k\le 100$。

对于测试点 $9\sim 10$，无特殊性质。

对于所有测试点，编号为奇数的测试点满足 $P=10^9+7$，编号为偶数的测试点满足 $5\times 10^8\le P\le 10^9+7$。

对于所有的测试数据，保证 $1\le n\le 10^{18},1\le a\le 10^9,0\le k\le 2000$。

【来源】

？？？