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⋯。

用 fn表示斐波那契数列的第 n 项，则有：$f1 = f2 = 1，fn = fn−1 + fn−2 (n>2)$。

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

用 fn表示新数列的第 n 项，则有：$f1 = f2 =1，fn=af(n−1)+bf(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