# PROBLEM LINKS

Practice

Contest

# DIFFICULTY

HARD

# EXPLANATION

We are given that the answer will have fewer than 700 digits (the maximum is actually 613). It suffices to find all solutions to the equation 2^{a}3^{b}5^{c}7^{d}=P(mod 1000000007), subject to a/3+b/2+c+d<700. To do this, we first make a list of all values Q such that 2^{a}3^{b}=Q(mod 1000000007) has a solution with a/3+b/2<700. We sort this list, so we can perform fast searches on it using binary search. Now for all possible values c and d with c+d<700 we check if 5^{-c}7^{-d}P is in our sorted list. If so, we've found a potential solution to the problem. Given candidate values of a, b, c, and d, we compute the answer by greedily taking as many 9's as possible, then as many 8's as possible, and so on, down to 2. Note that the digit 1 is never used, except when P itself is 1 or 0.

# SETTER'S SOLUTION

Can be found here.

# TESTER'S SOLUTION

Can be found here.

asked
**27 Nov '12, 19:23**

0★admin ♦♦

19.7k●350●498●541

accept rate:
35%