测试数据来自 nnu_contest/1255

E. NJNU

时间限制:1s

空间限制:64MB

题目描述

用字符N、J、U构成一个长度为$n$的字符串$S$，且$S$含有 子串 'NJNU'。

共有多少个这样的字符串？由于答案可能过大，请对$10^9+7$取模。

例如：$NJNUN$是符合条件的字符串，但$NJNNU$不是

输入格式

一个正整数$n$

输出格式

一个正整数，表示答案，请对$10^9+7$取模。

样例输入1

5

样例输出1

6

样例1解释

第一位任取，最后四位为NJNU，有三种；

前四个字符为NJNU，最后一位任取，有三种；

故一共有6种。

样例输入2

6

样例输出2

27

样例输入3

8

样例输出3

404

样例输入4

114

样例输出4

871106847

样例输入5

2021

样例输出5

55733383

数据范围及限制

对于所有的测试点，$1\le n\le 2*10^5$

拓展

• Bonus: 你能对于 $1\le n \le 2^{63}$ 解决这个问题吗？

• 当然，在这场比赛中你只需要考虑 $1\le n\le 2*10^5$