#P1506. 2023.08.27-ZJTD秋招第二场-第三题-奇数偶数位

2023.08.27-ZJTD秋招第二场-第三题-奇数偶数位

题目描述

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

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

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

输入描述

一行正整数n1e9n \leq 1e9

输出描述

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

答案可能太大,请对109+710^9+7取模后再输出。

样例

输入

2

输出

2025

输入

3

输出

40500