题目描述

求$\red{n}$位十进制正整数中出现奇数个$\red{7}$的数的个数，如果这个数字太大，请输出这个数对$\red{1000,000,000}$取模的结果。

输入格式

输入只有一行，包含一个正整数$\red{n}$。

输出格式

输出共一行，包含一个整数，表示奇数个$\red{7}$的数的个数对$\red{99,999,997}$取模的结果。

样例

输入样例

2

输出样例

17

提示

对于$\red{30\%}$的数据，$\red{2≤n≤6}$；

对于$\red{70\%}$的数据，$\red{2≤n≤1000,000}$；

对于$\red{100\%}$的数据，$\red{2≤n≤1000,000,000}$。