HZNUOJ

God and Goddess II

Tags:
Time Limit:  1 s      Memory Limit:   32 MB
Submission:12     AC:3     Score:99.75

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.

Author

CHEN, Yupeng