题目背景

第一轮决斗结束后，魔法师们进入了更考验策略的第二轮。

在这一轮中，每位魔法师要连续施放 $N$ 次招式。招式按照威力分为 $1,2,\ldots,N$ 级。高阶招式不能凭空出现：如果使用了第 $k$ 级招式，那么第 $k-1$ 级招式也必须出现；并且，为了让魔力顺利衔接，第 $k$ 级招式的第一次出现必须早于第 $k-1$ 级招式的最后一次出现。

裁判想知道一共有多少种合法的施法序列。由于方案数极其庞大，你只需要输出该方案数去掉末尾所有 $0$ 后的最后五位。

题目描述

给定一个正整数 $N$。

考虑所有长度恰好为 $N$ 的整数序列

其中每个元素均满足

一个序列被称为合法序列，当且仅当对于每个在序列中出现过的整数 $k\ge 2$，都满足：

1. 数字 $k-1$ 也在序列中出现过；
2. 数字 $k$ 的第一次出现位置，小于数字 $k-1$ 的最后一次出现位置。

设合法序列的总数为 $S$。

将 $S$ 的十进制表示末尾所有连续的 $0$ 删除，再取所得整数的最后五位，记为 $P$。请输出 $P$。

如果删除末尾的 $0$ 后，所得整数不足五位，则直接输出这个整数，不补前导零。

输入格式

输入仅一行，包含一个正整数 $N$。

输出格式

输出一行一个整数，表示 $P$。

样例

输入

9182

输出

48832

样例说明

合法序列的数量等于 $9182!$。将 $9182!$ 末尾所有连续的 $0$ 删除后，其最后五位为 48832。

数据范围

对于全部数据：

本数据包按以下子任务组织：