Description

Dark Souls is a famous video game. The main character in Dark Souls 3 is known as

" Ashen one ". Today you are the Ashen one.

---

You are in a 5*5 room. You are at the

position ( 1, 1 ) -- the top left corner -- and you want to reach the

position ( 5, 5 )-- the lower right corner.

There's no obstacle in the room but monsters. If you and the monster are at the same position, you need to fight it.

The rule of fighting is Turn-based. You can always attack first, if the monster didn't die after your attack, then it's the monster's turn to attack you and so on. 

There is always only two result after a fight, you died or the monster died.

Note that once you lost your hp you can't restore it.

Find out if you can reach the position ( 5,5 )

 

 

Input

input contain servel lines.

First line contains three integers.

The Hp, attack of Ashen one and k( 1 <= k <= 25 ) the number of monsters.

Following k lines each lines contains four integers.

The Hp, attack of i-th monster and the position x,y of i-th monster.

All numbers are >= 1 and in the range of int

Output

If you can reach the position ( 5 ,5 ) print "HEIR OF FIRE DESTROYED"

otherwise print "YOU DIED"

remember to print \n at the end of output

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

After some hard work of finding his queen, Knuckles finally arrived NTHU!

Knuckles is exhausted. He wants to grab some delicious food. However, as all of us know......

THERE IS NO "DELICIOUS" FOOD IN HSINCHU.

(Actually there are some restaurants that are not bad. But just "not bad"...)

 

 

This truth, which is cruel, hits Knuckles pretty hard. Knuckles doesn't give up and start his journey of finding delicious food in Hsinchu. 

However, the more he goes out and seeks, the truth is just getting more clear...

The i-th time that those bad-taste restaurants Knuckles found is F_i . Knuckles found that F₁ = 1, F₂ = 1, and F_i = F_i-1 + F_i-2 .

The more Knuckles goes out, the more bad-taste restaurants he found.

He is tired of finding more and more bad restaurants. He just wants to know there are how many bad restaurants when he goes out for the i-th time.

---

• There's a sequence F.
• F₁ = 1, F₂ = 1, F_i = F_i-1 + F_i-2.
• Find out F_i .

Hint：

Input

The input contains multiple lines, ended by EOF.

Every line contains an integer i.

1 <= i <= 10¹⁸.

There will be at most 20 lines.

Output

Output F_i.

Because F_i might be too big, the answer should mod 10⁹+7, which means you should output F_i % (10⁹+7).

Remember to print a '\n' at the end of the output.

Sample Input  Download

Sample Output  Download

Tags

Discuss