# 数据恢复

- 参考时间限制：**0.5 秒**（[评测环境与性能](../../../docs/评测环境与性能.md)）。
- 实际时限：在目标环境实测标准程序最慢测试文件的中位时间，乘以 2，再按 0.5 秒向上取整。
- 内存限制：**128 MB**。

## 背景故事

电脑店的一位客户把一个整数的阶乘保存在硬盘里。病毒损坏了文件的前缀，但末尾的一段数字仍然正确。技术员知道原来的整数，也知道保留下来的数字，希望恢复整个阶乘。

## 形式化问题描述

给定非负整数 $n,k$ ，以及十进制字符串 $s$ ，其中 $s$ 恰好由 $n!$ 的最后 $k$ 位组成。

设 $D$ 为 $n!$ 的十进制位数。保证 $0\le D-k\le15$ ，即至多缺失最前面的 $15$ 位。输出 $n!$ 的完整十进制表示。

约定 $0!=1$ .字符串 $s$ 可以包含前导零；当 $k=0$ 时，它是空字符串。

## 输入格式

第一行两个整数 $n,k$ .第二行是恰有 $k$ 个数字的字符串 $s$ ；当 $k=0$ 时，第二行为空行。

## 输出格式

输出一行，为 $n!$ 的完整十进制表示，不含前导零。

## 样例 1

### 输入

```text
9 1
0
```

### 输出

```text
362880
```

## 样例 2

### 输入

```text
20 17
32902008176640000
```

### 输出

```text
2432902008176640000
```

## 样例 3

### 输入

```text
20 4
0000
```

### 输出

```text
2432902008176640000
```

## 样例 4

### 输入

```text
0 0

```

### 输出

```text
1
```

## 样例解释

样例 1 中，$9!=362880$ ，保留的最后一位是 $0$ .

样例 2 保留了 $20!$ 的最后 $17$ 位，缺失的前缀是 `24` .样例 3 的后缀有四个零，它们不能在读取时丢失。样例 4 中，后缀为空，仍应输出 $0!=1$ .

## 数据范围与保证

对 100% 的数据：$0\le n\le500000$ ，$\max(0,D-15)\le k\le D$ ，其中 $D$ 是 $n!$ 的十进制位数。输入后缀正确，长度恰好为 $k$ .

| 分值比例 | 额外条件 |
| --- | --- |
| 100% | 无额外条件 |