题号：NC54761
时间限制：C/C++/Rust/Pascal 4秒，其他语言8秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
时间限制：C/C++/Rust/Pascal 4秒，其他语言8秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
wnm是个极度自恋的家伙，他总觉得自己txdy，这一次他想制作一串长度为n且只由'w','n','m'三个字符雕刻而组成的手链（手链是一条长度为n的直链）来彰显自己的地位，但是制作一个这样的手链对wnm来说太简单了，于是他给自己添加了一些限制条件：
1.这个手链里三个连续的字符不能是三个一样的字符，如 'w w w','m m m'等。
2.如果连续三个字符任意两个不相同的话，字符'm'不能出现在中间位置（如：'w m n'）。
3.连续的三个字符里第一个和最后一个是m的话中间不能是w或n（如：'mnm'等）。
wnm想知道到底有多少种组成手链的方案（由于答案过大 需要mod 1e9+7）？
1.这个手链里三个连续的字符不能是三个一样的字符，如 'w w w','m m m'等。
2.如果连续三个字符任意两个不相同的话，字符'm'不能出现在中间位置（如：'w m n'）。
3.连续的三个字符里第一个和最后一个是m的话中间不能是w或n（如：'mnm'等）。
wnm想知道到底有多少种组成手链的方案（由于答案过大 需要mod 1e9+7）？
输入描述:
第一行有一个整数
输出描述:
输出可能的方案总数。