问题描述

小红定义一个排列的权值为：将排列从左到右的所有元素拼接成一个大整数，对 $5$ 取模得到的值。 现在求所有长度为 $n$ 的排列的权值之和（对 $10^9+7$ 取模后输出）。

例如当 $n=3$ 时，所有排列拼接成的数有：$123, 213, 132, 312, 231, 321$，它们对 $5$ 取模的值分别为 $3,3,2,2,1,1$，总和为 $12$。

输入格式

一个整数 $n$（$1 \le n \le 2\times10^5$）。

输出格式

一个整数：所有长度为 $n$ 的排列的权值之和，对 $1000000007$（即 $10^9+7$）取模后的结果。

样例输入 1

3

样例输出 1

12

样例输入 2

114514

样例输出 2

301557575

说明

样例1说明：排列 $123, 213, 132, 312, 231, 321$ 对 $5$ 取模分别为 $3,3,2,2,1,1$，和为 $12$。