toys

After throwing a party at his house, Gigel and his kindergarten colleagues must move all the toys from the living room to his room. In order to get from the living room to Gigel's room, the children must pass through a hallway of length L.
Gigel has N friends (which he has numbered from 1 to N) and still has M toys to move. His friends have already begun work and are somewhere between the living room and Gigel's room. Some of them already have a toy to move, and the others are returning to the living room to pick up a new toy.
We will identify the hallway position of a child by the distance they are away from Gigel's room. More specifically, for each child i we will determine two values, d_i and t_i, with meaning: d_i represents the distance child i is away from Gigel's room and t_i=1, if child i is transporting a toy from the living room to Gigel's room, and respectively t_i=0 if child i is returning from Gigel's room to the living room with no toy.
Each child takes a toy to Gigel's room, returns to the living room to pick up a new toy and repeats this process until all toys are moved.
Gigel analyzes the configuration of the N friends and notices that d₁=S and t₁=1 (meaning that the first child is at distance S from Gigel's room and is carrying a toy). For the other children (i=2, 3, ..., N) values d_i and t_i can be determined using the following formulas (values X, Y, Z, V are known):
d_i = ( X * d_i-1 + Y * ( i - 1 ) ) % ( L - 1 ) + 1
t_i = ( Z * d_i-1 + V * ( i - 1 ) ) % 2
By a % b we understand the remainder of a's division to b.

Task

Help Gigel determine the minimum amount of time in which all the toys are returned to his room.

Input Data

Line one of input file toys.in contains three positive integers: N, L and M, each separated by a space. The following line contains five positive integers, S,X,Y,Z,V, each separated by a space, with the meaning in the task.

Output Data

File toys.out will contain a single line with the minimum amount of time in which all the toys will be moved to Gigel's room.

• 1 <= M <= 2 000 000 000
• 0 <= N <= 2 000 000
• 0 <= L <= 2 000 000
• 0 <= X, Y, Z, V <= 2 000 000
• 0 <= S <= L
• The result will be in 64 bit integer data types.
• Children move one distance unit in a one time unit, and dropping off or picking up a toy does not use up time.

  Time limit: 0.2 seconds/test

Diaconu Adrian Paul
University of Bucharest, Mathematics & IT Department
ditzone@gmail.com