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

Description

This problem is partial judge!

We will give you the "inorder" and "preorder" of a tree.

You need to construct a tree by the "inorder" and "preorder" we give you and print the "postorder".

There are three function you need to complete.

Node* buildTree(int *inorder, int *preorder, int *inorder_start, int inorder_end*);

function to construct the tree.

void showPostorder(Node *root)

function to print the postorder

void freeTree(Node *root)

function to free the tree

 

Notice that the the final testcase has small memory limit. If you don't free your tree you will get memory limit exceeded

 

 

 

 

 

(The tree for sample input 1)

(The tree for sample input 2)

Input

 

There are multiple testcases. The testcases will end with EOF.

Each testcase contains three lines.

First line only contains one integer n(1 <= n <= 100) which means the number of nodes in the tree.

Second line contains n integers which in the range of int. Standing for the "inorder".

Third line contains n integers which in the range of int. Standing for the "preorder".

It is guarnteed that no same number will appear in one tree.

Output

For each testcase output the "postorder" of the tree.

You have to output in this form:

testcase<id>: <postorder sequence>

Replace <id> and <postorder sequence> into the i-th testcase and the correct postorder sequence.

Each number in postorder sequence should be followed by a single blank(even the last number).

If you have further questions, please refer to sample output.

Sample Input  Download

Sample Output  Download

Partial Judge Code

12390.c

Partial Judge Header

12390.h

Tags

Discuss