PRIME - Factorial factorisation

no tags 

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 non-decreasing order. If no factorisation can be found print No solution.

Example

Input:
9

Output:
9! = 2! * 3! * 3! * 7!



hide comments
(Tjandra Satria Gunawan)(曾毅昆): 2012-12-17 10:10:22

Haha, Now I know why this problem was in tutorial, because full brute-force 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: 2012-12-17 10:26:13
Francky: 2012-12-16 22:35:30

@Ashish Lavania : spaces are just like the output example. Don't forget like me the "9! = " ;-)
Edit : Oh I see, just one space on each side of the "*" (unlike the example given), but I think it isn't important.

Last edit: 2012-12-16 22:37:39
Ashish Lavania: 2012-12-16 21:35:36

What about the spaces ?
Where should there be spaces
Please reply ASAP
Thanks Francky but Im still stuck :-(
FORGOT TO TAKE INPUT :- Mega TROLL!!!

Last edit: 2013-05-04 07:25:22
Robert Gerbicz: 2012-12-16 18:23:21

16! = 2! * 5! * 14!
(Choose the formula that has got fewer terms.)
For n=13: No solution
(You can't use n! in the factorisation.)

Last edit: 2012-12-16 18:24:59
(Tjandra Satria Gunawan)(曾毅昆): 2012-12-16 18:09:59

Thanks for the answer Robert Gerbicz, finally I got AC ;-)

Last edit: 2012-12-17 10:21:55
Robert Gerbicz: 2012-12-16 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:2011-03-19
Time limit:0.193s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:ASM32-GCC MAWK BC C-CLANG C++ 4.3.2 CPP CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV JAVA JS-MONKEY KTLN NIM NODEJS OBJC OBJC-CLANG OCT PAS-GPC PAS-FPC PICO PIKE PROLOG PYPY PY_NBC R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET
Resource:olymp.krsu.edu.kg