Start: Mar, 27, 2015 15:30:00
2015年省赛最终选拔赛Round#3
End: Mar, 27, 2015 18:30:00
Time elapsed:
Time remaining:

God and Goddess II 1498

Time Limit:  1 s      Memory Limit:   32 MB
Submission:0     AC:0     Score:1

Description

As we know, CJC and LOY are the god and goddess in our ACM Team.

We can’t use their names (only “cjc” and “loy”, not include “ccj”,”lyo”, ect.) when we writing texts as it’s a disrespect behavior (of course, this text is an exception). For example, if you write “loyiloveyou”, it’s discourteous, but if you write “oyiloveyou” or “oyliloveyou”, it’s polite.

So if you want to write some sentences which is no more than n characters (only consist of lowercase alphabet) and show your respect for the god and goddess, how many different sentences can you write?

Input

n (1<=n<=10000).

Output

A number, indicates the different sentences (a sentence has at least one character) you can write. The number may very large, please mod 1000000007.

Samples

input
3 4
output
18276 475148

Hint

 For the first test cases, 18276=26*26*26+26*26+26-2.