AOJ 4291 - Linear recursive sequence

Linear recursive sequence

Time Limit: 3000ms

Memory Limit: 131072KB

This problem will be judged on HDU. Original ID: 4914
64-bit integer IO format: %I64d Java class name: Main

Submit Status Statistics

Font Size:

Description

A well-known linear recursive sequence f(n) is defined as follows.

For k≤0, f(k)=1
For k≥1, f(k)=a*f(k - p)+b*f(k - q).

Given n,a,b,p,q, find the value of f(n) modulo 119.

Input

The input consists of several tests. For each tests:

5 integers n,a,b,p,q (1≤n≤10⁹,0≤a,b≤10⁹,1≤p<q≤10⁴).

Output

For each tests:

A single integer f(n).

Sample Input

1 1 1 1 2
1000000000 1 2 3 4

Sample Output

2
100

Source

2014 Multi-University Training Contest 5