Dom and Brian have come across this locker which they can't open. The fate of the mission depends on it. They have to open it at any cost. Tej has found the pattern in the combination. The pattern goes like this, given a number X between 0 to 10^9+6 find smallest positive integer Y such that the products of digits of Y modulo 10^9+7 is X. This Y is the combination of the lock. Help Dom and Brian open this safe.

Input: A single integer, X.

Output: A single integer, Y.

Input: 0 <= X <= 10^9+6