该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Background

斐波那契数列都不会就shi吧）┭┮﹏┭┮保命TAT

Description

给定 $f(1),f(2)$
对于 $i>=3$ 都有 $f(i)=a*f(i-1)+b*f(i-2)$
求出 $f(n)$%m

Format

Input

第1行：$n,m$
第2行：$a,b$
第3行：$f(1),f(2)$

Output

$f(n)$%m

Sample 1

Input

5 114514
1 1
1 1

Output

5

Limitation

对于20%的数据，$n<=10^6$
对于40%的数据，$n<=10^9$
对于另外20%的数据，$b=0$
对于100%的数据，$3<=n<=10^18 , 1<=m,a,b,f1,f2<=10^9$

$500ms$ for each test case.

Source

@zyc Original