Background

Special for beginners, ^_^

Description

现在，我们有一个马和一个电话垫(如下所示)，马只能站在数字单元格上。你可以将马放置在任何数字单元格上，然后你应该执行n-1次移动来获得长度为n的号码。马所有的移动应该是符合规则的有效的移动。马在一次移动的过程中可以经过符号单元格，但必须保证这次移动结束后马站在数字单元格上。

给定一个整数n,请你计算可以得到多少个长度为n的数字串。由于答案可能很大，请你输出答案对10^9+7取模后的结果。

Format

Input

输入一个自然数n。

Output

输出答案对10^9+7取模后的结果。

Samples

1

10

2

20

Limitation

对于30%的数据：1 <= n<=10

对于50%的数据：1 <= n<=200

对于70%的数据：1 <= n <= 50000

对于100%的数据：1 <= n <= 1000000