C-Style Loops

Time limit1sMemory limit128 MB

Summary

Count the iterations of a C for loop whose counter wraps modulo 2^k, or report FOREVER if it never reaches the stopping value.

Level: Medium5 of 10
Topics: Math, Number theory, Implementation, Simulation
Solved: No attempts yet

Problem

You are given a C-style for loop:

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

The loop initializes variable to A, then, while variable is not equal to B, repeatedly executes statement and increases variable by C. All arithmetic is performed on a $k$ -bit unsigned integer type modulo $2^k$ (that is, within the range $0 \le x < 2^k$ , taking remainders modulo $2^k$ ).

For the given $A$ , $B$ , $C$ , and $k$ , determine how many times statement is executed. If the loop never terminates, print FOREVER instead.

Input

The input consists of several instances. Each instance is given on a single line containing four integers $A$ , $B$ , $C$ , and $k$ separated by a single space. Here $k$ ( $1 \le k \le 32$ ) is the number of bits of the loop control variable, and $A$ , $B$ , $C$ ( $0 \le A, B, C < 2^k$ ) are the parameters of the loop.

The last line of the input contains four zeros; this line is not processed.

Output

Print one line for each instance. The $i$ -th line contains the number of times statement is executed in the $i$ -th instance (a single integer), or FOREVER if the loop never terminates.

Examples1

Example 1

Input

Expected output

0
2
32766
FOREVER