H. *【矩阵乘法】5：Gauss Fibonacci

传统题

1000ms

128MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

【题意】by lixuanjing(改编自hdu 1588)

有一个 $g$ 数组， $f$ 数组。

$g_i =k*i+b$ 。

$f_0=0,f_1=1,f_i=f_{i-1}+f_{i-2}(i \ge 2)$ 。

求 $f_{g_0}+f_{g_1} + \dots + f_{g_{n-1}}$ 的值，结需要 $mod \ M$ 。

一行四个整数 $k(1 \le k \le 100),b(1 \le b \le 150),n(n \le 10^9),M(M \le 10^9+7)$，四个整数意思如题意。

输出结果 $mod \ M$ 的值。

2 1 4 100