题目描述
蒸发器的密码提示是一个数字n，如果一个长度为n的数字串，每个位置都是0或者1，并且把它向左移动两位之后，和原数字串不会有同一个位置上下都是1的情况，那么就把这个数字串称作合法的数字串。而蒸发器的密码，就是长度为n的合法数字串的数量，对1000000007取余数的结果。请你编写程序，求出蒸发器的密码。
输入
一个整数，表示蒸发器的密码提示n(1≤n≤1000000)。
输出
一个整数，表示蒸发器的密码。
样例输入
3样例输出
6