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

Example

Input:
9

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

Added by:Azat Taryhchiyev
Date:2011-03-19
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ADA95 ASM32 ASM64 GAWK BASH BF C CSHARP C99 CLPS CLOJURE LISP sbcl LISP clisp D ERL FSHARP FORTRAN GO HASK ICON ICK JS-RHINO LUA NEM NICE OCAML PERL PERL6 PHP PRLG-swi PYTHON PYTHON3 RUBY SCALA SCM guile SCM qobi SED ST TCL WHITESPACE
Resource:olymp.krsu.edu.kg

hide comments
2022-01-06 14:54:18
can someone give me a hint ?
i tried brute forcing but it works only when there are two factorials. is there some math stuff that i dont get ?
google is stupid like me
2012-12-17 10:10:22 (Tjandra Satria Gunawan)(曾毅昆)
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
2012-12-16 22:35:30 Francky
@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
2012-12-16 21:35:36 Ashish Lavania
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
2012-12-16 18:23:21 Robert Gerbicz
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
2012-12-16 18:09:59 (Tjandra Satria Gunawan)(曾毅昆)
Thanks for the answer Robert Gerbicz, finally I got AC ;-)

Last edit: 2012-12-17 10:21:55
2012-12-16 14:18:28 Robert Gerbicz
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).
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.