站外题求助

第1题 字符传输 查看测评数据信息 在网络上传输由a,b,c三种字母组成的长为n的字符串，若字符串中有两个a连续出现，则网络上不能传输，问有多少种不同的传输方式？如：aba是合法的长度为3的字符串，而baa则是非法的长度为3的字符串。

输入格式 一个整数n。 1 <= n <= 100

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

输入/输出例子1 输入：

2

输出：

8

可以提供一下思路吗？说是要用dp