我真的不想写字符串（hard version）
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
题目描述
这天$xiudu$在写字符串相关的题时，发现字符串专题是真的很难，他信心大失，他想请你帮他解决这个问题，这个问题是给你一个长度$n$，你需要构造一种长度为$n$的字符串，该字符串只由$A$，$B$，$C$组成，但是每三个连续的字符只能存在${''AAA'',''BBB'',''CCC'',''AAB'',''BAA'',''BBA'',''ABA'',''ABB'',''BCC'',''BBC''}$这十种组合，你需要计算你能构造出多少个这样串。由于答案可能过大，所以请对$10^9+7$取模。
输入格式
第1行输入一个数。
输出格式
输出一行。
样例
1
3
来源
2022 HGNU-SWUT暑假联合集训