E NJNU
测试数据来自 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\)