Factorial Recovery¶
- Indicative time limit: 0.5 seconds (environment and measurements).
- Actual limit: measure the reference solution on the target system, take the largest median time over test files, multiply by 2, and round up to a multiple of 0.5 seconds.
- Memory limit: 128 MB.
Story¶
A computer-shop customer stored the factorial of an integer on a hard drive. A virus damaged the beginning of the file, but a suffix of its decimal digits is still correct. The technician knows the original integer and the surviving suffix, and wants to restore the complete factorial.
Formal Problem Statement¶
You are given nonnegative integers \(n,k\) and a decimal string \(s\) consisting of exactly the last \(k\) digits of \(n!\) .
Let \(D\) be the number of decimal digits of \(n!\) . It is guaranteed that \(0\le D-k\le15\) : at most the first \(15\) digits are missing. Output the complete decimal representation of \(n!\) .
By convention, \(0!=1\) . The string \(s\) may contain leading zeros. When \(k=0\) , it is empty.
Input Format¶
The first line contains two integers \(n,k\) . The second line contains the string \(s\) of exactly \(k\) digits; it is an empty line when \(k=0\) .
Output Format¶
Output the complete decimal representation of \(n!\) on one line, without leading zeros.
Sample 1¶
Input¶
9 1
0
Output¶
362880
Sample 2¶
Input¶
20 17
32902008176640000
Output¶
2432902008176640000
Sample 3¶
Input¶
20 4
0000
Output¶
2432902008176640000
Sample 4¶
Input¶
0 0
Output¶
1
Sample Explanation¶
In sample 1, \(9!=362880\) , whose final digit is \(0\) .
Sample 2 preserves the last \(17\) digits of \(20!\) ; the missing prefix is 24 . Sample 3 contains four zero digits in its suffix, and all four must be retained when reading it. In sample 4, the suffix is empty and the answer is still \(0!=1\) .
Constraints and Guarantees¶
For all test cases: \(0\le n\le500000\) and \(\max(0,D-15)\le k\le D\) , where \(D\) is the number of decimal digits of \(n!\) . The supplied suffix is correct and has exactly \(k\) digits.
| Score share | Additional conditions |
|---|---|
| 100% | None |