Description

Once there was a kind-hearted woodcutter. Though he is poverty-stricken, he is extraordinarily bright. But he was so poor that he have nothing but the bare walls in one's house with only one dilapidated axe to keep his life, and if he had not the dilapidated axe, he would starve to death. One day, sunny, Birds' twitter and fragrance of flowers, compassionate and wise but poor woodcutter to cut firewood. He walked up to a small river, and when he was crossing the bridge, the accident happened, and his axe suddenly fell off. He was so sad that he cried on the bridge.

At the time, the river suddenly shining bright, come out a very amiable of white hair of the elderly.

"what's wrong with you, young man”, The old man said kindly

” my ax fell” He said sadly.

“Don't worry, as long as you answer my question, I will give you an axe. My question is as follows:

We have been given a cycle.

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

A number which starts by setting Num to value A,while Num is not equal to B, repeats statement followed by increasing the Num by C ,we want to know how many times does the statement get executed for particular values of A, B and C, assuming that all arithmetics is calculated in a k-bit unsigned integer type (with values $0 \leq x < 2^k$) modulo $2^k$.”

Now compassionate and intelligentbut poor woodcutter asked you for help, can you help him

Format

Input

The input consists of several instances. Each instance is described by a single line with four integers $A, B, C, k$ separated by a single space. The integer $k (1 \leq k \leq 32)$ is the number of bits of the control Num of the loop and $A, B, C (0 \leq A, B, C < 2^k)$ are the parameters of the loop.

The input is finished by a line containing four zeros.

Output

The output consists of several lines corresponding to the instances on the input. The $i$-th line contains either the number of executions of the statement in the $i$-th instance (a single integer number) or the word $FOREVER$ if the loop does not terminate.

Samples

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

0
2
32766
FOREVER