Background

为了跟上快速的技术发展，熊猫先生需要备份他电脑上的所有数据，以便他可以对电脑进行全面升级。 由于升级需要一些时间，他将购买ACM（计算机维护协会）提供的存储服务器来临时存储他的数据。

Description

尽管ACM提供任意大小的存储服务器，但ACM希望鼓励更多购买相同大小服务器的批量购买，因为这样可以节省成本。 购买一组每台可以存储 $M$ 字节的存储服务器的价格包括基础价格 $M$ 美元加 该大小服务器的购买数量 $N$ 美元。

熊猫先生希望存储总共 $K$ 字节的数据，为了方便跟踪服务器，他希望以最低的价格购买一组相同大小的存储服务器来存储 $K$ 字节的数据。 然而，熊猫先生感到有必要不浪费任何空间。因此，他要求购买的服务器的总存储空间必须正好是 $K$ 字节。

随着技术的飞速发展，需要备份的数据也呈指数式增长，所以$K$ 可能非常大。幸运的是，$K$总可以分解成若干个100以内质数的乘积。给出 $K$ 的质因数分解。请你帮助熊猫先生计算存储他的数据所需的最低价格。 由于最低价格可能相当大，所以对质数 $10^9+7$ 取模后输出。

Format

Inpu1

输入包括一行，其中包含一个长度是偶数且不超过2000的字符串，表示 $K$ 的质因数分解。 从第一个数字开始，每两个连续的数字对，表示一个质因数。因此，长度为 $N$ 的输入将有 N/2 个质因数。

保证给定的所有质因数都是质数，且 $K$ 最多有 $10^{12}$ 个约数。同一个质因数最多出现 $100$ 次。

Output

输出一行，作为一个整数输出最小成本。

Samples

1311

24

Limitation

1s, 1024KiB for each test case.