Description

可怜的蚁人进入量子领域后，黄蜂女被灭霸的一个响指带走，导致可怜的蚁人困在了量子领域。

蚁人在量子领域里推算出了一个“（3^n）mod 1000000007” 的式子，现在只要蚁人能够把这个式子的答案算出来，他就可以从量子领域里逃出去。现在蚁人需要你的帮助，你能帮助他吗？

Format

Input

输入只有一行，输入一个数 n ，n 的范围（1<= n <=10^100000)

Output

输出只有一行，输出这个式子的答案

Samples

3

27

Hint