题目描述

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

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

【名词解释】排列：长度为 n 的排列是由 1,2,…,n 这 n 个数，按任意顺序组成的数组(每个数恰好出现一次)。

例如，(2,3,1,5,4)是一个长度为5的排列；而(1,2,2)和(1,3,4)都不是排列，因为前者存在重复元素，后者包含超出范围的数。

格式要求

输入格式

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

输出格式

输出一个整数，代表答案对 1e9+7 取模后的值。

样例

3

12

114514

301557575

样例解释

长度为 3 的排列拼接而成的数：123,213,132,312,231,321。

对5取模的值之和为3+3+2+2 +1+1=12。

数据范围

30% 数据：1 ≤ n ≤ 10

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