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

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

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

用 $f_n$ 表示新数列的第 $n$ 项，则有：$f_1 = f_2 = 1$，$f_n =a f_{n-1} + bf_{n-2} (n>2)$。

输入格式

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

输出格式

输出 $f_n$ 对 $p$ 取模的值。

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

样例输入

3 1 1 1000

样例输出

2