题目描述

在网络上传输由 a,b,c 三种字母组成的长为 n 的字符串，若字符串中有两个 a 连续出现，则网络上不能传输，问有多少种不同的传输方式？

如：aba 是合法的长度为 3 的字符串，而 baa 则是非法的长度为3的字符串。

输入格式

一个整数n 。

数据范围

1 <= n <= 100

输出格式

一个整数，表示不同的传输方式的数量，答案 %10000007 。

样例

2

8