#P16391. 第二轮决斗

第二轮决斗

题目背景

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

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

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

题目描述

给定一个正整数 NN。

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

a1,a2,…,aN,a_1,a_2,\ldots,a_N,

其中每个元素均满足

1≤ai≤N.1\le a_i\le N.

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

  1. 数字 k−1k-1 也在序列中出现过;
  2. 数字 kk 的第一次出现位置,小于数字 k−1k-1 的最后一次出现位置。

设合法序列的总数为 SS。

将 SS 的十进制表示末尾所有连续的 00 删除,再取所得整数的最后五位,记为 PP。请输出 PP。

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

输入格式

输入仅一行,包含一个正整数 NN。

输出格式

输出一行一个整数,表示 PP。

样例

输入

9182

输出

48832

样例说明

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

数据范围

对于全部数据:

1≤N≤1016.1\le N\le 10^{16}.

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

子任务 分值 数据范围
1 10 1≤N≤1001\le N\le 100
2 20 1≤N≤1051\le N\le 10^5
3 30 1≤N≤10121\le N\le 10^{12}
4 40 1≤N≤10161\le N\le 10^{16}