Consider the sequence of numbers x0, x1, ..., xn-1, generated with the next formula:

x0 = p,

xi = (a * xi-1 * xi-1 + b * xi-1 + c) mod m, where 0 < i < n

Create a Linked List from these numbers: List = x0 → x1 → ... → xn-1.

Let k = xn mod n. If xn < m / 2, let tail → next of your list points to the k-th element. Otherwise tail → next = NULL. Setup the value of tail → next according to this condition.

Consider the example: p = 1, a = 1, b = 1, c = 1, m = 100, n = 5. Here List = 1 → 3 → 13 → 83 → 73, xn = 3, so k = 3 < 100 / 2 = m / 2 and tail → next points to the third element that equals to 83 (elements' positions in a List starts from 0).

Write a method hasCycle that determines if a List has a cycle in it.

Write the code according to the next interface:

class Node

{

public:

int data;

Node *next;

Node() : next(NULL) {};

Node(int data, Node *next = NULL) : data(data), next(next) {};

};

class List

{

public:

Node *head, *tail;

List() : head(NULL), tail(NULL) {};

void addToTail(int val); // Add number val to the end of the Linked List

int hasCycle(void) // Returns 1 if a List has a cycle, and 0 otherwise

};

You can create (use) additional methods if needed.

Input

One line contains six numbers: p, a, b, c, m, n. All numbers are integers in the range from 0 to 1000, m and n are greater than 0.

Output

Print 1 if the Linked List has a cycle and 0 otherwise.