题目描述

编译器之谜：我们提供了一种C语言风格的for循环，类型为：

for (variable = A; variable != B; variable += C)
  statement;

即，一个循环开始时将变量值设置为值$A$，当变量不等于$B$时，重复执行语句并使变量增加$C$。

我们想知道在特定$A、B$和$C$的值下，该语句被执行了多少次，假设所有的算术运算都是在$k$位无符号整数类型中进行（其值范围为$0 \le x < 2^k$），模数为$2^k$。

以上题意可以简化为：

给出$A,B,C,k$,求$X$,使得$(A+C*X)$%$2^k=B$

输入格式

输入包含多个实例。

每个实例由一行描述，其中包含四个整数$A, B, C, k$，它们之间用一个空格隔开。整数$k$（$1 \le k \le 32$）是循环控制变量的位数，而$A, B, C（0 \le A, B, C < 2^k）$是循环的参数。

输入以一行包含四个零的行结束。

输出格式

输出包含几行，每行对应输入中的一个实例。

第$i$行包含第$i$个实例中语句执行的次数（一个整数），如果循环不终止，则输出单词FOREVER。

样例

3 3 2 16
3 7 2 16
7 3 2 16
3 4 2 16
0 0 0 0

0
2
32766
FOREVER

数据范围

• $1 \le k \le 32$
• $0 \le A, B, C < 2^k$

来源

• poj2115
• 信息学奥赛之数学一本通
• stong9070整理