题目描述

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

用 fₙ表示斐波那契数列的第n项，则有:f₁=f₂=1,fₙ=fₙ₋₁+fₙ₋₂(n>2)。

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

用 fₙ 表示新数列的第n项，则有:f₁=f₂=1,fₙ=afₙ₋₁+bfₙ₋₂(n>2)。

输入格式

输入每行包含 4 个整数n（1≤n≤100），a（1≤a≤10），b（1≤b≤10），p（1≤p<2000）。

输出格式

输出 fₙ 对p取模的值。

输入样例 #1

3 1 1 1000

输出样例 #1

2

输入样例 #2

1 1 1 2

输出样例 #2

1

输入样例 #3

2 2 4 99

输出样例 #3

1

数据范围

用 fₙ表示斐波那契数列的第n项，则有:f₁=f₂=1,fₙ=fₙ₋₁+fₙ₋₂(n>2)。

用 fₙ 表示新数列的第n项，则有:f₁=f₂=1,fₙ=afₙ₋₁+bfₙ₋₂(n>2)。

输入每行包含 4 个整数n（1≤n≤100），a（1≤a≤10），b（1≤b≤10），p（1≤p<2000）。