描述

一个编译器谜题：我们有一个C语言风格的for循环，格式如下

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

即，循环开始时将变量赋值为A，只要变量不等于B，就重复执行语句，并在每次循环后将变量增加C。我们需要知道对于给定的A、B和C值，这个语句会被执行多少次。假设所有算术运算都在一个$k$位无符号整数类型（取值范围为$0 \leq x < 2^k$）中进行，并以$2^k$为模。

输入

输入包含多个实例。每个实例由一行四个整数A、B、C、k组成，用单个空格分隔。整数$k$（$1 \leq k \leq 32$）是循环控制变量的位数，而A、B、C（$0 \leq A, B, C < 2^k$）是循环的参数。

输入以一行四个$0$结束。

输出

输出包含若干行，分别对应输入中的每个实例。第$i$行输出第$i$个实例中语句的执行次数（一个整数），或者如果循环不会终止，则输出单词FOREVER。

输入数据 1

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

输出数据 1

0  
2  
32766  
FOREVER  

来源

捷克技术大学公开赛 2004