题目描述

小名定义一个排列的权值为：从左到右将所有元素拼接之后，得到的新整数对5取模的值。

现在需要计算长度为n 的所有排列的权值之和，由于结果可能很大，请将答案对1000000007取模后输出。

【名词解释】排列：长度为 n 的排列是由1,2,…,n 这 n 个数，按任意顺序组成的数组(每个数恰好出现 一次)。例如，(2,3,1,5,4)是一个长度为5的排列；而(1,2,2)和(1,3,4)都不是排列，因为前者存在重复元素，后者包含超出范围的数。

输入格式

第一行输入一个整数n (1≤n≤2×10⁵)。

输出格式

输出一个整数，代表答案对1000000007取模后的值。

3

12

</p>

提示

说明长度为3的排列拼接而成的数：123,213,132,312,231,321。对5取模的值之和为3+3+2+2 +1+1=12。

30%数据：1≤ n≤10，100%数据：1≤n≤2×10⁵

输入：
114514
输出：
301557575

【样例说明】原题面样例头排版为「示 例 示 例 1」，已还原为两组独立样例。

【备注】原题面样例块排版有缺陷，此处按题意还原。

来源

2025-2026教师解题