PRIME  Factorial factorisation
Factorial n! of an integer number n ≥ 0 is defined recursively as follows:
0! = 1
n! = n * (n  1)! 
While playing with factorials chEEtah noticed that some of them can be represented as a product of other factorials, e.g. 6! = 3! * 5! = 720. Such factorisation helps chEEtah to simplify a certain class of equations he is working on during his research.
So he needs a program that finds a compact factorisation of a given factorial or determines that it is impossible if that is the case. If there are more than one factorisation the program has to find such that contains the minimum number of terms. For example, 10! can be factorised in two different ways: 10! = 6! * 7! = 3! * 5! * 7!. The first factorisation contains only two terms and should be preferred to the second one. If there are several factorisations with the same minimum number of terms then any optimal solution is acceptable.
Input
Input contains the only integer 2 ≤ n ≤ 1000 which factorial n! should be factorised.
Output
Output should contain the optimal factorisation in the format shown in the samples. The factorisation terms should go in nondecreasing order. If no factorisation can be found print No solution.
Example
Input:
9
Output:
9! = 2! * 3! * 3! * 7!
hide comments
(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
20121217 10:10:22
Haha, Now I know why this problem was in tutorial, because full bruteforce algorithm optimized with recursive precomputation got AC in 0.02s :P But thanks for moving this problem to classical, i agree.. This problem isn't easy ;) Last edit: 20121217 10:26:13 

Francky:
20121216 22:35:30
@Ashish Lavania : spaces are just like the output example. Don't forget like me the "9! = " ;)


Ashish Lavania:
20121216 21:35:36
What about the spaces ?


Robert Gerbicz:
20121216 18:23:21
16! = 2! * 5! * 14!


(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
20121216 18:09:59
Thanks for the answer Robert Gerbicz, finally I got AC ;) Last edit: 20121217 10:21:55 

Robert Gerbicz:
20121216 14:18:28
Moved to classic, the problem is not trivial. Note that if no factorisation can be found print "No solution" (so without dot at the end of line). 
Added by:  Azat Taryhchiyev 
Date:  20110319 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  ASM32GCC MAWK BC CCLANG C++ 4.3.2 CPP CPP14 CPP14CLANG COBOL COFFEE DCLANG DDMD DART ELIXIR FANTOM FORTH GOSU GRV JAVA JSMONKEY KTLN NIM NODEJS OBJC OBJCCLANG OCT PASGPC PASFPC PICO PIKE PROLOG PYPY PY_NBC R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET 
Resource:  olymp.krsu.edu.kg 