神奇的%系列三

Time Limit: 2000/1000MS (Java/Others) Memory Limit: 65536/32768KB (Java/Others)

Problem Description

在计算机的世界里,%不是百分比,而是除法取余哟!
比如:

4 % 2 = 0

5 % 3 = 2

我们定义一个f(n)函数,f(n) = a * f(n - 1) + b * f(n - 2), f(1) = c, f(2) = d.
问f(n)在模1000000007情况下的最小循环节。即求最小的m,使对任意的n有f(n) % 1000000007 = f(n + m) % 1000000007.

Input

输入有多组数据,对于每组数据:
一行有三个整数a, b, c, d(1 <= a, b, c, d <= 1000). a, b, c, d描述如上。

Output

对于每组数据,输出最小循环节的长度。如果没有循环节,那么输出-1

Sample Input

1 1 1 1
1 2 3 4

Sample Output

2000000016
1000000006

Source

zju_xxx

Manager

Information
Solved Number30
Submit Number74
Problem Tags
math
number theory
No tag edit access
温馨提示:AC后可以编辑标签哦. ^-^
Login
LoginCancel