### 问题描述 $ymt$ 很喜欢自己的名字，爱屋及乌，所以她很喜欢只包含 $y$，$m$，$t$ 三个字母的字符串，而且她认为如果字符串中有两个连续的 $y$ ，将会出现一些奇怪的歧义，她不希望出现这种情况。现在她想让你帮她求一下长度为 $n$ 的字符串有多少个是她很喜欢且不会出现歧义的。答案对 $1000000007$ 取模。 ### 输入格式 一行一个正整数 $n$，代表字符串长度。 ### 输出格式 输出一个数，代表字符串数量，对 $1000000007$ 取模。 ### 样例输入 ``` 3 ``` ### 样例输出 ``` 22 ``` ### 数据范围 $1 \leq n \leq 10^6$。 样例中合法的字符串有 $ymm,ymt,ymy,ytt,ytm,yty,mmm,mmy,mmt,myt,mym,mtt,mty,mtm,ttt,tty,ttm,tmm,tmy,tmt,tym,tyt$。这些字符串既满足只包含 $y,m,t$ 又不存在两个连续的 $y$ 。