Jo-jo is a lonely man with a clever and eternally living cat. However, the cat feels Jo-jo is too lonely, and it decides to leave him; but it also hates to leave him forever.

Then the cat decides to revisit Jo-jo according to the following fixed scheme.

• It leaves on the t-th day of the week (1 to 7 inclusive).
• Its first revisit with Jo-jo is p days later.
• The time span between revisits are in a geometric sequence.

For example

1. First revisit: p days after its leaving.
2. Second revisit: p q days after the first revisit.
3. Third revisit: p q^2 days after the second revisit, and so on.

Please calculate on which day of the week (still 1 to 7, inclusive) the cat revisits Jo-jo for the n-th time.

The numbers p, q, t, n are all positive integers. As usual, t is given as integer, but **p, q, and n are given in a string represented in decimal ways. The length of such strings are all divisible by 3, padded with leading zeros. ** (This format might be a hint, but also might be a misleading to the solution. )

Restrictions: t must be in [1, 2, 3, 4, 5, 6, 7]; the length of any string p, q, or n is guaranteed not to exceed 10002. Since the strings are too long, _large random tests do not reveal their values in test messages. _

Well, corner cases will also be tested, but all numbers are guaranteed to be positive integers, and the strings are always in the described format.

Warning

NEVER even try to calculate the exact numbers involved. The numbers are far too huge.

You have to find out the patterns to solve the problem.

Clarification

The time span is counted as difference of moments. For example, between today (the eighth of August) and tomorrow (the ninth) there is 1 day.

Example Test

p = '001', q = '002', t = 2, n = '004'

1. Today the cat leaves. It is Tuesday (well, for example; you can read it anyway you want, and it will not change your result).
2. One day later, it will be the cat's first revisit -- Wednesday.
3. Two days later, the second revisit -- Friday.
4. Four days later, the third revisit -- Tuesday.
5. Eight days later, the fourth revisit -- Wednesday.

So please return 3 as integer.