You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

给定一个只含数字的字符串， 例如$1233$ , 其奇数位的数位和为:$1+3 = 4$ , 偶数位的数位和位$2+3 = 5$ (奇数位指下标是奇数的位置，偶数位指下标是偶数的位置，下标从1开始。)

奇偶权值$f(s)$为:奇数位的和乘以偶数位的和。 $f(1233) = 4 * 5 = 20$

请计算所有长度为$n$的数字串(可以有前导零)的奇偶权值的和是多少?

输入描述

一行正整数$n \leq 1e9$

输出描述

输出一个非负整数，表示权值和。

答案可能太大，请对$10^9+7$取模后再输出。

样例

输入

2

输出

2025

输入

3

输出

40500