2451: Linear recursive sequence
内存限制:128 MB
时间限制:10.000 S
评测方式:文本比较
命题人:
提交:0
解决:0
题目描述
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.
输入
The input consists of several tests. For each tests:
5 integers n,a,b,p,q (1≤n≤109,0≤a,b≤109,1≤p<q≤104).
输出
For each tests:
A single integer f(n).
样例输入 复制
1 1 1 1 2
1000000000 1 2 3 4
样例输出 复制
2
100