Given a sequence of natural numbers .

Find it's N'th term.

a1=3, a2=9, a3=30, a4=101, a5=358, a6=1443... ...,aN

Input

Single line containing a natural number N

Output

Print N'th term of the sequence modulo 10^9+7.

Constraints

• 1 N 100

Example

Input: 5 Output: 358

Given a sequence of natural numbers .

Find it's N'th term.

a1=3, a2=9, a3=30, a4=101, a5=358, a6=1443... ...,aN

Input

Single line containing a natural number N

Output

Print N'th term of the sequence modulo 10^9+7.

Constraints

• 1 N 100

Example

Input: 5 Output: 358 q2

Mohit and his girlfriend are playing a game named 'Ascending sort'. The norms of the game are as follows :

Initialy N integers are taken randomly and are kept on the table. The one who makes these N numbers as acsending numbers wins the game. Both play turn by turn and in a single turn they can add or subtract 1 to any single integer present on the table and they are restricted to change the positions of integers during their turn.

Two numbers a[i], a[i+1] are said to be acending number in the given order if a[i] i+1] or if they are equal.

Mohit wants to get a kiss from his girlfriend, so he plans to lose the game and make his girlfriend win. Mohit needs your help to know who should start first so that he gets a kiss. Help Mohit in acheiving his objective in minimum steps.

Input

• First line contains T the number of test cases.
• Next T lines contains N.
• Next line contains N integers (A[1],A[2],...,A[N]) which are kept on the table.

Output

• Print "MOHIT" or "GFRINED" depending upon who should start first.

Constraints

• 1 T 10
• 1 N 5000
• -1000000000 A[i] 1000000000

Example

Input: 2 2 -5 0 4 3 0 -5 3 Output: MOHIT MOHIT

Explanation

Case 1 : -5 and 0 are already as ascending numbers. Mohit gets a kiss if he starts first. Since, he is unable to make any move.

Case 2 :3 turns required to turn 3 to 0 and then 5 turns to turn -5 to 0 so that they become 0 0 0 3 and are as ascending numbers.So to do this minimum number of turn is 8.