$m=1e9+7;@1=($2[2]=1)x2;map{$$_[$']=(${$_%3+1}[$'-$_]+${($_+1)%3+1}[$'-$_])%$m for//..3}3..($n=<>);print+($1[$n]+$2[$n]+$3[$n])%$m