思路:数学题

由于求的是所有长度为$n$的数字的权值和。所以我们可以发现：对于任意一个偶数位（月光位）的状态，它会和所有奇数位（星光位）匹配组成一个数字，然后相乘求和。所以结论是分别计算星光位（奇数位）和月光位（偶数位）的和乘起来即可

举个例子，假设$n = 3$ , 那么假设星光位（第1、3位）为:$1\ 3$ . 那么月光位（第2位）可以是$0,1,...,9$ , 分别会组成$103,113,123,133,143,153,...,193$

他们的和就是:$(1+3) * (所有月光位的和)$

对于任意星光位，它都满足上面这种答案，所以答案就是$所有星光位的和*所有月光位的和$

题目内容

在一项深空通信实验中，工程师使用长度为 $n$ 的数字序列作为信号。序列的每个位置可以是 0 到 9 之间的任意数字（允许前导零）。

将信号序列从左至右依次标记：第 $1$ 位为“星光位”，第 $2$ 位为“月光位”，第 $3$ 位为“星光位”，第 $4$ 位为“月光位”，如此交替。记一个信号中所有星光位上的数字之和为星光能量 $A$，所有月光位上的数字之和为月光能量 $B$。该信号的综合能量定义为 $A \times B$。

请你计算所有可能的长度为 $n$ 的信号序列的综合能量之和。由于答案可能很大，请输出其对 $10^9+7$ 取模后的结果。

约束：$n$ 是一个正整数，且 $n \le 10^9$。

输入描述

输入包含一行，一个正整数 $n$，表示信号序列的长度。

输出描述

输出一个整数，表示所有可能信号的综合能量之和对 $10^9+7$ 取模后的结果。

样例1

输入

3

输出

40500

说明

当 $n=3$ 时，序列长度为 3。星光位为第 $1,3$ 位，共 $s = \lceil 3/2 \rceil = 2$ 个；月光位为第 $2$ 位，共 $m = \lfloor 3/2 \rfloor = 1$ 个。所有可能序列有 $10^3$ 种。综合能量总和可表示为 $s \times m \times 45^2 \times 10^{n-2}$，其中 $45$ 是单个位置数字之和（$0$ 到 $9$）。代入得 $2 \times 1 \times 2025 \times 10 = 40500$。对 $10^9+7$ 取模后结果仍为 40500。

样例2

输入

4

输出

810000

说明

当 $n=4$ 时，星光位和月光位各有 $2$ 个，即 $s=2, m=2$。总和公式为 $s \times m \times 45^2 \times 10^{n-2}$。代入得 $2 \times 2 \times 2025 \times 10^{2} = 4 \times 2025 \times 100 = 810000$。取模后仍为 810000。

样例3

输入

10

输出

499964566

说明

当 $n=10$ 时，星光位和月光位各有 $5$ 个，即 $s=5, m=5$。总和为 $5 \times 5 \times 2025 \times 10^{8} = 25 \times 2025 \times 10^8 = 50625 \times 10^8 = 5062500000000$。计算该值对 $10^9+7$ 取模：$5062500000000 \bmod (10^9+7) = 499964566$。