Problem D
Association of Computer Maintenance
In order to keep up with the rapid technological advancements, Mr. Panda needs to backup all the data on his computer to allow him to do a full upgrade of his computer. Since the upgrade will take some time, he will peruse the services of the company ACM (Association of Computer Maintenance) that provides storage servers for him to temporarily store his data.
Although ACM offers storage servers of any size, ACM wants to encourage more bulk purchases of servers of the same size as this saves cost. The cost of purchasing a set of storage servers that can each store $M$ bytes consists of a base cost of $M$ dollars plus $1$ dollar for every server of that size purchased.
Mr. Panda wants to store a total of $K$ bytes of data and in order to easily track the servers, he wants to purchase a set of storage servers of the same size to store the $K$ bytes of data using the least cost. However, Mr. Panda feels compelled not to waste any space. Thus, he requires that the total storage space of the servers purchased must be exactly $K$ bytes.
As storage space of technology increases exponentially with time, $K$ can be very large. You are given the prime factorization of $K$. Help Mr. Panda calculate the minimum cost required to store his data. As the minimum cost can be quite large, print the minimum cost modulo a prime number $10^9+7$.
Input
The input consists of one line with a string of even length consisting of at most $700$ representing the prime factorization of $K$. Every pair of two consecutive digits, starting from the first two digits, represents one prime factor. So input of length $N$ will have $N/2$ prime factors.
It is guaranteed that all the prime factors given are prime and that $K$ has at most $10^{10}$ divisors. Each prime factor will appear at most $100$ times.
Output
Output the minimum cost in one line as a single integer.
Sample Data Explanation
In the first example, $K = 2 \cdot 3 \cdot 2 = 12$, so buy three servers with $M = 4$ bytes. Mr. Panda pays $4$ dollars base cost plus $3$ dollars for three servers purchased, or a total of $4+3 = 7$ dollars. Mr. Panda can also buy four servers with $M = 3$ bytes with the same cost of $7$ dollars.
In the second example, $K = 13 \cdot 11 = 143$, so buy eleven servers with $M = 13$ bytes. Mr. Panda pays $13$ dollars base cost plus $11$ dollars for eleven servers purchased, or a total $13+11 = 24$ dollars. Mr. Panda can also buy thirteen servers with $M = 11$ bytes with the same cost of $24$ dollars.
In the third example, $K = 11$, so buy one server with $M = 11$ bytes. Mr. Panda pays $11$ dollars base cost plus $1$ dollar for one server purchased, or a total $11+1 = 12$ dollars. Note that although he can get a cheaper cost if he were able to purchase storage servers of different sizes, he cannot do so.
| Sample Input 1 | Sample Output 1 |
|---|---|
020302 |
7 |
| Sample Input 2 | Sample Output 2 |
|---|---|
1311 |
24 |
| Sample Input 3 | Sample Output 3 |
|---|---|
11 |
12 |
