You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

相信小伙伴们都学过斐波那契数列，它是这样的一个数列：1,1,2,3,5,8,13,21⋯。

用 $f_n$表示斐波那契数列的第 n 项，则有：$f_1 = f_2 = 1，f_n = f_{n−1} + f_{n−2} (n>2)$。

为了提高难度，决定修改公式，如下：

用 fn表示新数列的第 n 项，则有：$f1 = f2 =1，f_n=a*f_{n−1}+b*f_{n−2} (n>2)$。

输入格式

输入每行包含 4 个整数 n(1≤n≤10)，a(1≤a≤10)，b(1≤b≤10)，p(1≤p≤2000)。

输出格式

输出fn对 p 取模的值。

输出时每行末尾的多余空格，不影响答案正确性

样例

3 1 1 1000

2