【题意】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

21