# Calculating Permutations on nxnxn Rubik's cube



## Sharkretriver (Jul 21, 2010)

anybody know how to calculate the number of permutations on an nXnXn 6-coloured rubik's cube?
(sort like this:
odd:
even: )


----------



## hawkmp4 (Jul 21, 2010)

Can you do it for a 5x5? 6x6? 7x7?
Just generalise that process for nxn.


----------



## Christopher Mowla (Jul 21, 2010)

Chris Hardwick came up with a formula. It's on his section on speedcubing.com.


----------



## hawkmp4 (Jul 21, 2010)

He's looking for permutations, though. That formula factors in orientation.


----------



## cmhardw (Jul 21, 2010)

hawkmp4 said:


> He's looking for permutations, though. That formula factors in orientation.



In my formula, in the numerator, replace \( (24\times 2^{10}\times 12!)^{(n\ mod\ 2)} \) with \( (4\times 12!)^{(n\ mod\ 2)} \) and also delete the \( 3^6 \) term. This new formula will calculate only permutations and ignore orientations.

Chris


----------



## Sharkretriver (Jul 21, 2010)

is there a differnence betweeen permutations, orientations and combinations :confused:


----------



## irontwig (Jul 21, 2010)

Sharkretriver said:


> is there a differnence betweeen permutations, orientations and combinations :confused:



Permutations concerns where pieces are supposed to be, orientations which way they should be facing and combinations both.


----------



## Sharkretriver (Jul 21, 2010)

epic formula but what does modulo mean? (I really have to learn more)


----------



## irontwig (Jul 21, 2010)

Sharkretriver said:


> epic formula but what does modulo mean? (I really have to learn more)



http://en.wikipedia.org/wiki/Modular_arithmetic


----------



## Christopher Mowla (Jul 21, 2010)

\( \text{AmodB}=A-B\times floor\left( \frac{A}{B} \right) \), and floor is the greatest integer function. Mod is the remainder of a quotient. You can type Chris' formula into wolframalpha, and it is able to calculate large numbers and even gives their designated name.


----------



## Rinfiyks (Jul 21, 2010)

Is that the floor function which 24! and 4! have been raised to?


----------



## Christopher Mowla (Jul 21, 2010)

Yes, the brackets \( \left\lfloor \text{ } \right\rfloor \) symbolize the floor function.


----------



## Kirjava (Jul 21, 2010)

irontwig said:


> Sharkretriver said:
> 
> 
> > is there a differnence betweeen permutations, orientations and combinations :confused:
> ...




Actually, I've seen permutations generally used to mean both aswell.


----------



## Rinfiyks (Jul 21, 2010)

cmowla said:


> You can type Chris' formula into wolframalpha



With great difficulty


----------



## Christopher Mowla (Jul 21, 2010)

Rinfiyks said:


> cmowla said:
> 
> 
> > You can type Chris' formula into wolframalpha
> ...


Yeah, you've got to know the syntax.

Here is Chris' formula which takes into account orientations as well.
Here is his adjusted formula that ignores orientations (that is, if I understood the changes he said to be made).

So, from the first formula (which I think Sharkretriver was really after):
2X2X2, 3X3X3, 4X4X4, 5X5X5, 6X6X6, 7X7X7, 10X10X10, 100X100X100, 1000X1000X1000, etc.


----------



## Charlie (Jun 17, 2011)

I don't really get most of this stuff.. 
I can understand the math of calculating combinations and restrictions of corners and edges moving in pairs. But wich part of the formula restrict x y z (orientation of the cube)?? Thanks


----------



## cmhardw (Aug 2, 2011)

Charlie said:


> I don't really get most of this stuff..
> I can understand the math of calculating combinations and restrictions of corners and edges moving in pairs. But wich part of the formula restrict x y z (orientation of the cube)?? Thanks


 
I can't believe I missed this question for so long :fp

If you look at my formula for the number of possible positions to a standard n x n x n Rubik's cube:
\( F(n) = \frac{(24*12!*2^{10})^{n (mod 2)}*7!*3^6*(24!)^{\lfloor\frac{n^2-2n}{4}\rfloor}}{(4!)^{6\lfloor\frac{(n-2)^2}{4}\rfloor}} \)

The portion that makes sure there are no overcounts considering x,y,z rotations of the cube is:
\( (24*12!*2^{10})^{n (mod 2)}*7!*3^6 \)

This term counts all possible positions of corners (if n is even), or corners and central edges (if n is odd).

In order to see how this avoids overcounting we will consider two cases:

Case 1:
If n is an even number (n=2k where k is a natural number), then we have:
\( (24*12!*2^{10})^{2k (mod 2)}*7!*3^6 = 7!*3^6 \)

There are only 7!*3^6 different possible positions for 8 corners, taking into account cube rotations as overcounting as well as the cube laws about twists of the corners.

If you don't see this, try to start with \( 8!*3^8 \) and figure out how this is an overcount by a factor of 72.

Case 2:
If n is an odd number (n=2k+1 where k is a natural number), then we have:
\( (24*12!*2^{10})^{2k + 1 (mod 2)}*7!*3^6 = (24*12!*2^{10})*7!*3^6 = 8!*3^7*12!*2^{10} \)

This is the number of ways that the corners and central edges can be permuted on an odd n x n x n cube, assuming that the central most centers are fixed, and define the solved state.

Just as we did for corners on an even cube, it would seem initially that the 8 corners and 12 edges should have the following number of possible positions:
\( 8!*3^8*12!*2^{12} \)

However, this is an overcount by a factor of 12. The reason why is based off of cube laws for rotations of corners, flips of edges, and parity restrictions for the corners and central most edges.

I know this maybe doesn't explicitly answer your question, but you can find a more detailed explanation on Ryan Heise's page describing the fundamental cube laws.


----------



## Charlie (Aug 4, 2011)

It was a great explanation. Thanks.


----------



## Christopher Mowla (Sep 26, 2011)

@cmhardw (and anyone else who understands these formulas for number of permutations on the nxnxn cube),

I have a question regarding the formula for the nxnxn supercube. However, I first am going to show how I approached the regular nxnxn first (my formula is correct to my knowledge).

Here's my formula for the non-supercube (not simplified), [Link]
\( F\left( n \right)=\frac{\left( 8!\times 3^{7} \right)\left( \frac{24!}{\left( 4! \right)^{6}} \right)^{\left\lfloor \frac{\left( n-2 \right)^{2}}{4} \right\rfloor }\left( 24!^{\left\lfloor \frac{n-2}{2} \right\rfloor } \right)\left( 12!\times 2^{11} \right)^{n\bmod 2}}{\left( 24-23\left( n\bmod 2 \right) \right)2^{n\bmod 2}} \)


Spoiler



Just to show those that may be interested,


Spoiler



\( \left\lfloor \frac{\left( n-2 \right)^{2}}{4} \right\rfloor =\left\lfloor \frac{n-2}{2} \right\rfloor \left( n-2-\left\lfloor \frac{n-2}{2} \right\rfloor \right) \)\( =\frac{n-2-\left| \sin \left( \frac{n\pi }{2} \right) \right|}{2}\left( n-2-\frac{n-2-\left| \sin \left( \frac{n\pi }{2} \right) \right|}{2} \right) \),
\( n\bmod 2=n-2\left\lfloor \frac{n}{2} \right\rfloor =-\left\lfloor \left\lfloor \frac{n}{2} \right\rfloor -\frac{n}{2} \right\rfloor =\left\lceil \frac{n}{2}-\left\lfloor \frac{n}{2} \right\rfloor \right\rceil =\left| \sin \left( \frac{n\pi }{2} \right) \right|\text{ for }n\in \mathbb{Z}^{+} \),
and \( \left( 24-23\left( n\bmod 2 \right) \right)=24^{\left| \cos \left( \frac{n\pi }{2} \right) \right|} \).

(Hence the formula can be written with trig functions instead of step functions)


*Corners*
\( \left( 8!\times 3^{7} \right) \)
There are 8 corners, hence 8! permutations of them.
The orientation of one corner depends on the other 7. Each corner can be twisted 3 ways, so we have \( 3\times 3\times 3\times 3\times 3\times 3\times 3=3^{7} \)

*Non-Fixed (NF) Center Pieces*
\( \left( \frac{24!}{\left( 4! \right)^{6}} \right)^{\left\lfloor \frac{\left( n-2 \right)^{2}}{4} \right\rfloor } \)

There are \( \left\lfloor \frac{\left( n-2 \right)^{2}}{4} \right\rfloor \) NF center orbits on the nxnxn cube. Each orbit is independent from the other (pieces from one NF center piece orbit cannot go into any other NF center pieces orbit), and each orbit contains (4 center pieces in each face)*(6 faces) = 24 pieces. 24 pieces can be arranged in 24! different ways. Because we are considering the non-supercube, then we reduce 24! by a factor of \( \left( 4! \right)^{6} \) before raising to \( \left\lfloor \frac{\left( n-2 \right)^{2}}{4} \right\rfloor \), the number of NF center orbits. The reason for the \( \left( 4! \right)^{6} \) reduction is because there are 4! ways to arrange the same color center pieces per NF center orbit (in any configuration) and there are 6 faces (hence raised to the 6th power).

*Wing Edges*
\( 24!^{\left\lfloor \frac{n-2}{2} \right\rfloor } \)
There are \( \left\lfloor \frac{n-2}{2} \right\rfloor \) orbits of wing edges on the nxnxn cube. Each orbit contains 24 pieces and each orbit is independent from the other (wing edges from one orbit cannot go into any other wing edge orbit). Hence each orbit of wings has 24! different permutations, and we raise it to the number of wing edge orbits, \( \left\lfloor \frac{n-2}{2} \right\rfloor \).

*Middle Edges* (Odd Cubes Only)
\( \left( 12!\times 2^{11} \right)^{n\bmod 2} \)
There are 12 edges and therefore 12! permutations of them. The orientation of one of the edges depends on the orientation of the other 11. An edge can be flipped in two ways, so we have \( 2\times 2\times 2\times 2\times 2\times 2\times 2\times 2\times 2\times 2\times 2=2^{11} \). Since middle edges are only in odd cubes, we raise all of this to n mod 2 which simply means for our purposes:
\( \left\{ \begin{matrix}
0,\text{ if }n\text{ is even,} \\
1,\text{ if }n\text{ is odd}\text{.} \\
\end{matrix} \right. \)
(Obviously anything^1 is itself and anything^0 = 1).


*Odd Permutation Reduction*
\( \frac{1}{2^{n\bmod 2}} \)
Middle Edges are in an odd permutation if and only if corners are in an odd permutation. The total number of odd permutations = the total number of even permutations and thus we divide by a factor of 2. However, we only do so if the cube is odd, so we raise it to n mod 2.

*Even Cube Symmetry Reduction*
\( \frac{1}{\left( 24-23\left( n\bmod 2 \right) \right)} \)

If _n_ is even, then there are 24 equivalent cube rotations in which the even cube can be in. Thus we need to have a function that yields the result:
\( f\left( n \right)=\left\{ \begin{matrix}
24,\text{ if }n\text{ is even,} \\
1,\text{ if }n\text{ is odd}\text{.} \\
\end{matrix} \right. \)
By how I showed the mod function works in the previous section, we can see that the piece above satisfies this requirement.


My formula for the nxnxn supercube (not simplified and which is equivalent to Chris Hardwick's) is: [Link]
\( F\left( n \right)=\frac{\left( 8!\times 3^{7} \right)\left( 12!\times 2^{11} \right)^{n\bmod 2}\left( 4^{6} \right)^{n\bmod 2}}{\left( 2^{n\bmod 2} \right)\left( 2^{\left\lfloor \frac{\left( n-2 \right)^{2}}{4} \right\rfloor } \right)\left( 2^{n\bmod 2} \right)} \)\( \text{ }\times \left( 24!^{\left\lfloor \frac{\left( n-2 \right)^{2}}{4} \right\rfloor } \right)\times \left( 24!^{\left\lfloor \frac{n-2}{2} \right\rfloor } \right)\times \frac{1}{24-23\left( n\bmod 2 \right)} \)


Spoiler



*Corners* (Same and non-supercubes)
\( \left( 8!\times 3^{7} \right) \)
There are 8 corners, hence 8! permutations of them.
The orientation of one corner depends on the other 7. Each corner can be twisted 3 ways, so we have \( 3\times 3\times 3\times 3\times 3\times 3\times 3=3^{7} \)

*Non-Fixed (NF) Center Pieces*
\( \left( 24!^{\left\lfloor \frac{\left( n-2 \right)^{2}}{4} \right\rfloor } \right) \)
Unlike the non-supercubes, we do not reduce this by a factor of \( \left( 4! \right)^{6} \) because center pieces are now unique to their positions.

*Wing Edges* (Same as non-supercubes)
\( 24!^{\left\lfloor \frac{n-2}{2} \right\rfloor } \)
There are \( \left\lfloor \frac{n-2}{2} \right\rfloor \) orbits of wing edges on the nxnxn cube. Each orbit contains 24 pieces and each orbit is independent from the other (wing edges from one orbit cannot go into any other wing edge orbit). Hence each orbit of wings has 24! different permutations, and we raise it to the number of wing edge orbits, \( \left\lfloor \frac{n-2}{2} \right\rfloor \).

*Middle Edges* (Odd Cubes Only) (Same as non-supercubes)
\( \left( 12!\times 2^{11} \right)^{n\bmod 2} \)
There are 12 edges and therefore 12! permutations of them. The orientation of one of the edges depends on the orientation of the other 11. An edge can be flipped in two ways, so we have \( 2\times 2\times 2\times 2\times 2\times 2\times 2\times 2\times 2\times 2\times 2=2^{11} \). Since middle edges are only in odd cubes, we raise all of this to n mod 2 which simply means for our purposes:
\( \left\{ \begin{matrix}
0,\text{ if }n\text{ is even,} \\
1,\text{ if }n\text{ is odd}\text{.} \\
\end{matrix} \right. \)
(Obviously anything^1 is itself and anything^0 = 1).

*Fixed Center Pieces* (On Odd Cubes Only)
\( \left( 4^{6} \right)^{n\bmod 2} \)
There are 6 fixed center pieces on the odd nxnxn cube. Each stay fixed with respect to each other, and each can be rotated in 4 ways in their locations. Since each can be rotated in their locations 4 ways and there are 6 of them, there are \( 4^{6} \) possible ways this can be done.

*Odd Permutation Reduction*
a) \( \frac{1}{2^{n\bmod 2}} \) (Odd Cubes Only) (Same as the non-supercube)
Middle Edges are in an odd permutation if and only if corners are in an odd permutation. The total number of odd permutations = the total number of even permutations and thus we divide by a factor of 2. However, we only do so if the cube is odd, so we raise it to n mod 2.

b) \( \frac{1}{2^{n\bmod 2}} \) (Odd Cubes Only)
Fixed center pieces are in an odd permutation if and only if corners are in an odd permutation if and only if middle edges are in an odd permutation.
The total number of odd permutations = the total number of even permutations and thus we divide by a factor of 2. However, we only do so if the cube is odd, so we raise it to n mod 2.

c) \( \frac{1}{2^{\left\lfloor \frac{\left( n-2 \right)^{2}}{4} \right\rfloor }} \)
If corners are in an odd permutation, then all non-fixed (NF) center orbits are in an odd permutation. (For those who can't see this, just do R to a supercube and see that it does a circular 4-cycle of every NF center piece orbit. Furthermore, corners in an odd permutation does not make the permutation of wing edges odd because R does 2 4-cycles of each and every orbit of wing edges, which is an even permutation).

The total number of odd permutations = the total number of even permutations and thus we divide by a factor of 2 per NF center orbit. Hence we raise 2 to \( \left\lfloor \frac{\left( n-2 \right)^{2}}{4} \right\rfloor \), the number of center orbits on the nxnxn cube (odd and even).

*Even Cube Symmetry Reduction* (Same as the non-supercube)
\( \frac{1}{\left( 24-23\left( n\bmod 2 \right) \right)} \)

If _n_ is even, then there are 24 equivalent cube rotations in which the even cube can be in. Thus we need to have a function that yields the result:
\( f\left( n \right)=\left\{ \begin{matrix}
24,\text{ if }n\text{ is even,} \\
1,\text{ if }n\text{ is odd}\text{.} \\
\end{matrix} \right. \)
By how I showed the mod function works in the middle edges section, we can see that the piece above satisfies this requirement.


Now this is what I am questioning about the supercube formula. If you compare my supercube formula to Chris Hardick's, you will see they yield the same values.  Now that you've seen I have taken care of the NF center piece reduction factor, the fixed center piece reduction factor, and the middle edge reduction factor, all directly associated with an odd permutation of corners AND yielding a formula identical to Chris Hardwick's...

Assume the corners are in an even permutation now. Then assume that either the NF center pieces or the wings (it doesn't really matter) are in an odd permutation. Then the other is in an odd permutation too, that is, for cube sizes \( \ge \)the 5x5x5 supercube. 

I know it's very possible I have misinterprented the given values in my formula, but if not (meaning that my explanation of each factor of the formula is correct), shouldn't there be another odd permutation reduction factor of \( \frac{1}{2^{\left\lfloor \frac{n-2}{2} \right\rfloor }} \) for the 5x5x5 and greater cubes since the parity state of \( f\left( n,r \right)=n-2-2r\text{ }\left( n\ge 4,\text{ }r\ge 1,\text{ }n,r\in \mathbb{Z} \right) \) center orbits is changed to odd if the parity state of _r_ orbits of wings (in any of the \( 2^{\left\lfloor \frac{n-2}{2} \right\rfloor }-1 \) possible combinations) is changed to an odd permutation?


EDIT:
Clearly both of my formulas can be combined into one (no simplification applied)






From this, we can see that the factor increase from the regular nxnxn to the supercube nxnxn is
\( \frac{4^{6n\bmod 2}4!^{6\left\lfloor \frac{\left( n-2 \right)^{2}}{4} \right\rfloor }}{2^{n\bmod 2}2^{\left\lfloor \frac{\left( n-2 \right)^{2}}{4} \right\rfloor }}=3^{6\left\lfloor \frac{\left( n-2 \right)^{2}}{4} \right\rfloor }2^{17\left\lfloor \frac{\left( n-2 \right)^{2}}{4} \right\rfloor +11n\bmod 2} \)

Substituting in 7 for n, I got the same value mrCage got for "the number of solved positions for the 7x7x7" here. This is the link to my value (which matches it perfectly).

and 18698417887260966912 is the number of solved positions for the 5x5x5, etc.

But, until I can get someone to say with assurance that we don't need to multiply in the extra reducing factor, I am not sure these are the correct values either.


----------



## Christopher Mowla (Sep 27, 2011)

If we do need that odd permutation reduction factor, I have managed to make a function that outputs \( \frac{1}{2^{\left\lfloor \frac{n-2}{2} \right\rfloor }} \) for cube sizes 5 and greater and 1 for cube sizes 2-4. It is \( \frac{1}{2^{\left\lfloor \frac{n-2}{2} \right\rfloor -\left\lfloor \frac{4}{n} \right\rfloor +\left\lfloor \frac{2}{n-1} \right\rfloor }} \). [Link]


----------



## cmhardw (Sep 27, 2011)

Hi cmowla,

Very cool post! I like your approach for how you listed this formula, particularly your mention of using trig functions to avoid the step functions.

I did find a couple of points from your post that I don't fully agree with, though:



cmowla said:


> c) \( \frac{1}{2^{\left\lfloor \frac{\left( n-2 \right)^{2}}{4} \right\rfloor }} \)
> *If corners are in an odd permutation, then all non-fixed (NF) center orbits are in an odd permutation.* (For those who can't see this, just do R to a supercube and see that it does a circular 4-cycle of every NF center piece orbit. Furthermore, corners in an odd permutation does not make the permutation of wing edges odd because R does 2 4-cycles of each and every orbit of wing edges, which is an even permutation).



The bolded line is only true if _every_ wing orbit has even parity.



cmowla said:


> Assume the corners are in an even permutation now. Then assume that either the NF center pieces or the wings (it doesn't really matter) are in an odd permutation. Then the other is in an odd permutation too, that is, for cube sizes \( \ge \)the 5x5x5 supercube.



If the corners are in an even permutation, then it is impossible for all non-fixed centers to be in an odd permutation. This is because the parity of every x-center orbit will always match the parity of the corners. So if the corners have even parity, so too will every x-center orbit.

Also, what about cases where only some of the center orbits have even parity, and others have odd? Or cases where some of the wings orbits have even party, and others have odd?

More generally, and this result comes from my center parity matrix method, there are 2 situations where we can infer information about the parities of various orbits on the supercube:

1) If the parities of the corners and every wing orbit are known, then you can deduce the parity of every non-fixed center orbit.

2) If the parity of every non-fixed center orbit is known, then you can deduce the parity of the corners AND every wing orbit.



cmowla said:


> I know it's very possible I have misinterprented the given values in my formula, but if not (meaning that my explanation of each factor of the formula is correct), shouldn't there be another odd permutation reduction factor of \( \frac{1}{2^{\left\lfloor \frac{n-2}{2} \right\rfloor }} \) for the 5x5x5 and greater cubes since the parity state of \( f\left( n,r \right)=n-2-2r\text{ }\left( n\ge 4,\text{ }r\ge 1,\text{ }n,r\in \mathbb{Z} \right) \) center orbits is changed to odd if the parity state of _r_ orbits of wings (in any of the \( 2^{\left\lfloor \frac{n-2}{2} \right\rfloor }-1 \) possible combinations) is changed to an odd permutation


 
Your formula:


> \( f\left( n,r \right)=n-2-2r\text{ }\left( n\ge 4,\text{ }r\ge 1,\text{ }n,r\in \mathbb{Z} \right) \)



doesn't work for n=8 and r=2. On the 8x8x8 cube, if you change the parity of 2 wings orbits, then you change the parity of 4 center orbits. This can easily be seen using the 3x3 center parity matrix that represents the 8x8x8 cube like I detail in this thread. However, your formula would imply that if n=8 and r=2 we would change the parity of:
\( f\left( 8,2 \right)=8-2-2*2=2 \) center orbits.

As to your question, I don't think any special reduction is necessary for cubes greater than or equal to the 5x5x5 cube. The general result I listed earlier about deducing the parities of various pieces given certain information would prove this if I'm not mistaken.

As a side note, since not all parity orbit situations are possible (for example, the parities of each x-center orbit must match that of every other x-center orbit), then it's more effective to first permute the corners and the wings into any of their possible permutations (which as you mention these orbits are all independent of each other). However, due to the center parity matrix method, this then determines the parities of every non-fixed center orbit (and also the parity of the center twists of the fixed centers for odd cubes).


----------



## Christopher Mowla (Sep 28, 2011)

cmhardw said:


> Very cool post! I like your approach for how you listed this formula, particularly your mention of using trig functions to avoid the step functions.


Thanks! I knew you would like it.



cmhardw said:


> I did find a couple of points from your post that I don't fully agree with, though:
> 
> 
> cmowla said:
> ...


You're absolutely right. I can't believe I overlooked the fact that there can be no more than \( \frac{1}{2^{\left\lfloor \frac{\left( n-2 \right)^{2}}{4} \right\rfloor }} \) NF center orbits in an odd permutation because that IS the number of center orbits, period.

However, I did read your center parity matrix method, and I definitely agree with everything about it.



cmhardw said:


> Your formula:
> 
> 
> cmowla said:
> ...


Yeah, I can't believe I forgot to multiply that by _r_! So the correct formula is:
\( r\left( n-2-2r \right) \).

This formula actually is directly related to (but I found this formula by trying to find the number of center pieces in an odd permutation along with the wings) the concept you mention how the "click" of an X-center piece affects the parity of pieces in its intersecting row and column of the matrix. In fact, here is a good visual of how I came up with that formula. I know it's probably very basic for you, but I thought others might appreciate the simplicity of this explanation of why my formula for the number of NF center orbits affected by an odd permutation of wings is correct.

*Derivation*


Spoiler



If we take a solved 13x13x13, focusing on the NF center pieces only (we shade in the wings, corners, and fixed center piece), we have (n-2) = 13 - 2 = 11 center pieces in slice 2R.

Let’s start out by doing a quarter turn to slice 2R. Clearly the orbit of wing edges slice 2R has an odd permutation. 
[FONT=&quot]




[/FONT]
[FONT=&quot]
[/FONT]Now we highlight the rest of slice 2R.
[FONT=&quot]



[/FONT]
[FONT=&quot]
[/FONT] 

If we imagine doing the move U, (not that we actually make another move), we can clearly see that the center orbits affected will transfer to the bottom as well.

_NOTE: The row shown below (and for the remaining iterations) is a visual only. I understand perfectly well that a 2 4-cycle of X-center pieces is done in each (M+1)R slice we do and that there is a 4-cycle of the remaining center pieces in that slice. The representation does however accurately show how the parity state of inner layer slices are related with minimal thought._
[FONT=&quot]




[/FONT][FONT=&quot]
[/FONT] At the intersection of the yellow row and yellow column is an even permutation, namely, the X-center piece. You can think of the column and the row representing an odd permutation: where they intersect becomes an even permutation (analogous to your \( 0_{L} \) idea). Indicated by the color orange.
[FONT=&quot]



[/FONT]
[FONT=&quot]
[/FONT] If we reflect this now to the top, clearly (n-2)-2 center orbits in an odd permutation now in the yellow column (just focus on the yellow column, not its corresponding yellow row).
[FONT=&quot]



[/FONT]

Suppose we now choose another wing edge orbit.
[FONT=&quot]




[/FONT][FONT=&quot]
[/FONT] Now we identify the row and column affected by it (the intersection of the new colored row and the previous yellow row is indicated by the color light green).
[FONT=&quot]



[/FONT]
[FONT=&quot]
[/FONT] Again, if we imagine doing U, the slice affected gets transferred to the bottom, and their intersection is an X-center piece.
[FONT=&quot]



[/FONT]

But this transferring row also intersects a piece in the first slice (slice 2R) we did a quarter turn to.
[FONT=&quot]




[/FONT][FONT=&quot]
[/FONT] Reflecting this to the top, clearly we have (n-2)-2-2 center orbits left with an odd permutation in both slices. That is, 2(n-2-2(2)).
[FONT=&quot]



[/FONT]

[FONT=&quot]
[/FONT] If we choose yet another orbit of wings,
[FONT=&quot]



[/FONT]

And identify its column (its intersection of the previous two rows is indicated with the color light blue).
[FONT=&quot]




[/FONT][FONT=&quot]
[/FONT] And we also find its corresponding row by visualizing doing U (its intersection with the previously affected columns is indicated by light blue),
[FONT=&quot]



[/FONT]
[FONT=&quot]
[/FONT] As always, we take note of the intersection of the current row and column to be the X-center piece (pink),
[FONT=&quot]



[/FONT]

Finally, reflecting this to the top,
[FONT=&quot]




[/FONT][FONT=&quot]
[/FONT]Note that every color besides the yellow, red and dark blue represent NF center pieces in an even permutation. They are analogous to your \( 0_{L} \). In fact, the amount of these *pieces* (not the orbit number) for _r_ orbits of wings (no matter which combination we choose) can be represented by \( 8\sum\limits_{i=1}^{r}{2i-1}=8r^{2} \).


Just focusing on the indicated portion below,
[FONT=&quot]



[/FONT]

We now have exactly (13-2)-2-2-2=5 NF center orbits in an odd permutation *in each wing edge orbit we chose*. There are 5 dark blue center pieces (each indicating a NF center orbit) in slice 5R, 5 red center pieces (each indicating a NF center orbit) in slice 3R, and 5 yellow center pieces (each indicating a NF center orbit) in slice 2R.

Clearly there is a pattern and if we were to choose arbitrary wing edge orbits, the number of NF center orbits in an odd permutation with the wings would be the same for any combination of the same number of wing edge orbits. 

For example,
\( \left( \begin{matrix}
5 \\
3 \\
\end{matrix} \right)=10 \) different ways we could have selected 3 orbits of wings for this particular cube size because we have a total of 5 orbits of wings taking 3 at a time.

Hence the formula is \( r\left( n-2-2r \right) \).


.Therefore the minimum number of NF center orbits in an odd permutation along with wings is \( \left\lfloor \frac{n-2}{2} \right\rfloor \left( n-2-2\left\lfloor \frac{n-2}{2} \right\rfloor \right) \), and, more importantly, the maximum number of center orbits in an odd permutation with wings is \( \left\lfloor \frac{n}{4} \right\rfloor \left( n-2-2\left\lfloor \frac{n}{4} \right\rfloor \right)=\left\lfloor \frac{\left\lceil \left( \frac{n-2}{2} \right)^{2} \right\rceil }{2} \right\rfloor \).

(I'll eventually prove these in great detail.)

Now having given it some careful thought, I have come up with a way to verify that the reducing factor \( \frac{1}{2^{\left\lfloor \left( \frac{n-2}{2} \right)^{2} \right\rfloor }} \) is indeed correct (I was wrong to think we needed more).

Our goal is to determine the maximum number of parity situations on an nxnxn supercube. Specifically, how the combination of the wings and corners affect the parity of the NF center pieces (since I apparently covered the other parity cases well enough).

First of all, we consider the independent cases.

1) We need to know the maximum number of center orbits affected by wings (assuming the corners are in an even permutation).

I have already said that that amount is equal to \( \left\lfloor \frac{n}{4} \right\rfloor \left( n-2-2\left\lfloor \frac{n}{4} \right\rfloor \right)=\left\lfloor \frac{\left\lceil \left( \frac{n-2}{2} \right)^{2} \right\rceil }{2} \right\rfloor \).

2) The corners affect all \( \left\lfloor \frac{n-2}{2} \right\rfloor \) X-center piece orbits.

This leaves \( \left\lfloor \frac{n-2}{4} \right\rfloor \left( \left( n-2 \right)-2-2\left\lfloor \frac{n-2}{4} \right\rfloor \right)=\left\lfloor \frac{\left\lceil \left( \frac{n-4}{2} \right)^{2} \right\rceil }{2} \right\rfloor \) non X-center NF center orbits to be unable to be affected by even the worst odd permutation combination of wings (this amount is zero until you get to the 7x7x7 and higher supercubes).

By the way, the number of orbits of wings which cause the worst (maximal center orbits in an odd permutation) combination for the NF center orbits is:

\( f\left( n \right)=\left\{ \begin{matrix}
\left\lfloor \frac{n}{4} \right\rfloor ,\text{ if }n\text{ is not divisible by 4,} \\
\left\{ \left\lfloor \frac{n}{4} \right\rfloor -1,\left\lfloor \frac{n}{4} \right\rfloor \right\}\text{ if }n\text{ is divisible by 4}\text{.} \\
\end{matrix} \right. \)

(Thus two values for _r_ yields the maximum for cube sizes evenly divisible by 4.)

Regardless of where these extra NF center orbits are (the number is only important, and their number is very well defined since we know the maximum number of center orbits which wings can affect and the number of X-center orbits and we know the total amount of center orbits there are), if they have an odd permutation, it will be from the corners (and consequently, along with the X-center pieces, fixed center pieces on odd cubes, and middle edges on odd cubes). This is unquestionably true since the parity of the corners has the potential to affect the parity of all center orbits, if all orbits of wings are in an even permutation, that is.


----------



## Christopher Mowla (Sep 30, 2011)

*Rate of Change for the Number of Permutations Formula*

As I have mentioned in my post before the last one is that we can represent the formula for the nxnxn without using step functions. We can use continuous functions, .i.e., trig functions.

Formula for the Regular nxnxn. [Link]

\( \left( 8!\times 3^{7} \right)\left( \frac{24!}{4!^{6}} \right)^{\frac{1}{4}\left[ \left( n-1 \right)\left( n-3 \right)+\cos ^{2}\left( \frac{n\pi }{2} \right) \right]}24!^{\frac{n-2-\sin ^{2}\left( \frac{n\pi }{2} \right)}{2}}\left( \frac{12!\times 2^{11}}{2} \right)^{\sin ^{2}\left( \frac{n\pi }{2} \right)}\frac{1}{24^{\cos ^{2}\left( \frac{n\pi }{2} \right)}} \)​ 
If you clicked that link and scrolled down, you would have eventually come across the (first) derivative of the formula. For those who haven't had calculus, all we need to do to find the rate of change to a function once we have the derivative is to substitute the x-value (here, it's n, the degree of the cube) and obtain the rate of change/slope of the function (in our case, the formula for the number of permutations) at that specific point (in our case, the specific cube size).

Obviously that derivative is quite lengthy, and Mathematica (not Wolfram, the program Mathematica itself) gets overloaded on my computer for cube size n = 999.

For convenience to everyone who has Mathematica, here is the derivative ready to go. Just substitute values for _x_ (I'd recommend using Ctrl+H in Wordpad)and evaluate the cell, and you'll get the same results I show below (and other values for other cube sizes). (Note: I have the //N at the end, but you can remove it to get the exact values.)


Spoiler



2^(-15 + (-3 + x) (-1 + x) + 11 x - 2 Cos[(x Pi)/2]^2 + 9 Sin[(x Pi)/2]^2) 3^(-1 + (-3 + x) (-1 + x) + 5 x) 5^(-3 + (-3 + x) (-1 + x) + 2 x + Cos[(x Pi)/2]^2) 7^(-1 + x + (3 ((-3 + x) (-1 + x) + Cos[(x Pi)/2]^2))/4 + (-2 + x - Sin[(x Pi)/2]^2)/2) 11^(-2 + x + ((-3 + x) (-1 + x) + Cos[(x Pi)/2]^2)/2) 96577^(((-3 + x) (-1 + x) + Cos[(x Pi)/2]^2)/4 + (-2 + x - Sin[(x Pi)/2]^2)/2) (1 + 2 x) Log[3] + 2^(-15 + (-3 + x) (-1 + x) + 11 x - 2 Cos[(x Pi)/2]^2 + 9 Sin[(x Pi)/2]^2) 3^(-1 + (-3 + x) (-1 + x) + 5 x) 5^(-3 + (-3 + x) (-1 + x) + 2 x + Cos[(x Pi)/2]^2) 7^(-1 + x + (3 ((-3 + x) (-1 + x) + Cos[(x Pi)/2]^2))/4 + (-2 + x - Sin[(x Pi)/2]^2)/2) 11^(-2 + x + ((-3 + x) (-1 + x) + Cos[(x Pi)/2]^2)/2) 96577^(((-3 + x) (-1 + x) + Cos[(x Pi)/2]^2)/4 + (-2 + x - Sin[(x Pi)/2]^2)/2) Log[5] (-2 + 2 x - Pi Cos[(x Pi)/2] Sin[(x Pi)/2]) + 2^(-15 + (-3 + x) (-1 + x) + 11 x - 2 Cos[(x Pi)/2]^2 + 9 Sin[(x Pi)/2]^2) 3^(-1 + (-3 + x) (-1 + x) + 5 x) 5^(-3 + (-3 + x) (-1 + x) + 2 x + Cos[(x Pi)/2]^2) 7^(-1 + x + (3 ((-3 + x) (-1 + x) + Cos[(x Pi)/2]^2))/4 + (-2 + x - Sin[(x Pi)/2]^2)/2) 11^(-2 + x + ((-3 + x) (-1 + x) + Cos[(x Pi)/2]^2)/2) 96577^(((-3 + x) (-1 + x) + Cos[(x Pi)/2]^2)/4 + (-2 + x - Sin[(x Pi)/2]^2)/2) Log[2] (7 + 2 x + 11 Pi Cos[(x Pi)/2] Sin[(x Pi)/2]) + 2^(-15 + (-3 + x) (-1 + x) + 11 x - 2 Cos[(x Pi)/2]^2 + 9 Sin[(x Pi)/2]^2) 3^(-1 + (-3 + x) (-1 + x) + 5 x) 5^(-3 + (-3 + x) (-1 + x) + 2 x + Cos[(x Pi)/2]^2) 7^(-1 + x + (3 ((-3 + x) (-1 + x) + Cos[(x Pi)/2]^2))/4 + (-2 + x - Sin[(x Pi)/2]^2)/2) 11^(-2 + x + ((-3 + x) (-1 + x) + Cos[(x Pi)/2]^2)/2) 96577^(((-3 + x) (-1 + x) + Cos[(x Pi)/2]^2)/4 + (-2 + x - Sin[(x Pi)/2]^2)/2) Log[96577] ((1 - Pi Cos[(x Pi)/2] Sin[(x Pi)/2])/2 + (-4 + 2 x - Pi Cos[(x Pi)/2] Sin[(x Pi)/2])/4) + 2^(-15 + (-3 + x) (-1 + x) + 11 x - 2 Cos[(x Pi)/2]^2 + 9 Sin[(x Pi)/2]^2) 3^(-1 + (-3 + x) (-1 + x) + 5 x) 5^(-3 + (-3 + x) (-1 + x) + 2 x + Cos[(x Pi)/2]^2) 7^(-1 + x + (3 ((-3 + x) (-1 + x) + Cos[(x Pi)/2]^2))/4 + (-2 + x - Sin[(x Pi)/2]^2)/2) 11^(-2 + x + ((-3 + x) (-1 + x) + Cos[(x Pi)/2]^2)/2) 96577^(((-3 + x) (-1 + x) + Cos[(x Pi)/2]^2)/4 + (-2 + x - Sin[(x Pi)/2]^2)/2) Log[11] (1 + (-4 + 2 x - Pi Cos[(x Pi)/2] Sin[(x Pi)/2])/2) + 2^(-15 + (-3 + x) (-1 + x) + 11 x - 2 Cos[(x Pi)/2]^2 + 9 Sin[(x Pi)/2]^2) 3^(-1 + (-3 + x) (-1 + x) + 5 x) 5^(-3 + (-3 + x) (-1 + x) + 2 x + Cos[(x Pi)/2]^2) 7^(-1 + x + (3 ((-3 + x) (-1 + x) + Cos[(x Pi)/2]^2))/4 + (-2 + x - Sin[(x Pi)/2]^2)/2) 11^(-2 + x + ((-3 + x) (-1 + x) + Cos[(x Pi)/2]^2)/2) 96577^(((-3 + x) (-1 + x) + Cos[(x Pi)/2]^2)/4 + (-2 + x - Sin[(x Pi)/2]^2)/2) Log[7] (1 + (1 - Pi Cos[(x Pi)/2] Sin[(x Pi)/2])/2 + (3 (-4 + 2 x - Pi Cos[(x Pi)/2] Sin[(x Pi)/2]))/4)//N


With these very large numbers, we mainly pay attention to the power of ten they are.

Here are some of the rates of change (decimal form of the exact numbers).


Spoiler



n=2: 1.00644*10^8
n=3: 1.95718*10^21
n=4: 4.6708*10^47
n=5: 2.29032*10^76
n=6: 1.55307*10^118
n=7: 2.27539*10^162
n=8: 4.73234*10^219
n=9: 2.15956*10^279
n=10: 1.412862071588920*10^352
n=11: 2.041829565969861*10^427 
n=12: 4.250648102022849*10^515
n=13: 1.961573176908497*10^606
n=14: 1.307459144395711*10^710
n=15: 1.935819473534397*10^816
n=16: 4.146563061346539*10^935
n=17: 1.975599053252146*10^1057
n=18: 1.363218034588532*10^1192
n=19: 2.094148907347992*10^1329
n=20: 4.662632788088312*10^1479
n=21: 2.312628415760626*10^1632


I deduced the following pattern from the numbers above by:
1) Taking the list of powers of 10:
{8,21,47,76,118,162,219,279,352,...}
2) Finding delta list (a list showing the distance between each number)
{13, 26, 29, 42, 44, 57, 60, 73,...}
3) And then taking the difference of that list:
{13, 3, 13, 2, 13, 3, 13, ...}
which obviously has a pattern involving the numbers 13, 3 and 2.

This is what I came up with:


Spoiler



\( \begin{matrix}
2 & 8+13\left( 0 \right)=8 \\
3 & 8+13\left( 1 \right)=21 \\
4 & 8+13\left( 3 \right)+3\left( 0 \right)=47 \\
5 & 8+13\left( 5 \right)+3\left( 1 \right)=76 \\
6 & 8+13\left( 8 \right)+3\left( 2 \right)+2\left( 0 \right)=118 \\
\end{matrix} \)
\( \begin{matrix}
7 & 8+13\left( 11 \right)+3\left( 3 \right)+2\left( 1 \right)=162 \\
8 & 8+13\left( 15 \right)+3\left( 4 \right)+2\left( 2 \right)=219 \\
9 & 8+13\left( 19 \right)+3\left( 6 \right)+2\left( 3 \right)=279 \\
10 & 8+13\left( 24 \right)+3\left( 8 \right)+2\left( 4 \right)=352 \\
11 & 8+13\left( 29 \right)+3\left( 10 \right)+2\left( 6 \right)=427 \\
\end{matrix} \)
\( \begin{matrix}
12 & 8+13\left( 35 \right)+3\left( 12 \right)+2\left( 8 \right)=515 \\
13 & 8+13\left( 41 \right)+3\left( 15 \right)+2\left( 10 \right)=606 \\
14 & 8+13\left( 48 \right)+3\left( 18 \right)+2\left( 12 \right)=710 \\
15 & 8+13\left( 55 \right)+3\left( 21 \right)+2\left( 15 \right)=816 \\
\end{matrix} \)
\( \begin{matrix}
16 & 8+13\left( 63 \right)+3\left( 24 \right)+2\left( 18 \right)=935 \\
17 & 8+13\left( 71 \right)+3\left( 28 \right)+2\left( 21 \right)=1057 \\
18 & 8+13\left( 80 \right)+3\left( 32 \right)+2\left( 24 \right)=1192 \\
19 & 8+13\left( 89 \right)+3\left( 36 \right)+2\left( 28 \right)=1329 \\
\end{matrix} \)
\( \begin{matrix}
20 & 8+13\left( 99 \right)+3\left( 40 \right)+2\left( 32 \right)=1479 \\
21 & 8+13\left( 109 \right)+3\left( 45 \right)+2\left( 36 \right)=1632 \\
\end{matrix} \)
...
=
8+
13*{0,1,3,5,8,11,15,19,24,29,35,41,48,55,63,71,80,89,99,109,...}+
3*{0,0,0,1,2,3,4,6,8,10,12,15,18,21,24,28,32,36,40,45,...}+
2*{0,0,0,0,0,1,2,3,4,6,8,10,12,15,18,21,24,28,32,36,...}


We can find formulas for each of the three sequences just copying and pasting the first 20 values we have into Wolfram Alpha (in list form) and scroll down to the "possibly closed form" formula. For example, a formula for the sequence multiplied by 13. 
(The formula that link gives is a little different from the one I used, but they both work.)

We can use the same formula for the sequences multiplied by 2 and 3, just shifting n by an additional 2 for the sequence multiplied by the 2. When all of this is done,

\( 8+ \)
\( 13\left( \frac{1}{8}\left( 2n^{2}+\cos \left( n\pi \right)-9 \right) \right)+ \)
\( 3\left( -\frac{1}{8}\left( \sin \left( \frac{\left( n-3 \right)\pi }{2} \right)-\left( n-3 \right) \right)\left( \sin \left( \frac{\left( n-3 \right)\pi }{2} \right)+\left( n-3 \right)+2 \right) \right)+ \)
\( 2\left( -\frac{1}{8}\left( \sin \left( \frac{\left( n-5 \right)\pi }{2} \right)-\left( n-5 \right) \right)\left( \sin \left( \frac{\left( n-5 \right)\pi }{2} \right)+\left( n-5 \right)+2 \right) \right) \)

We can simplify and get the approximation formula.

* My Approximation Formula 
for the Power of Ten of the Rate of Change Values
of the Regular nxnxn Cube
*\( n\ge 2 \)[Link]

\( \frac{1}{16}\left( 62n^{2}-56n-4\cos \left( \frac{n\pi }{2} \right)+21\cos \left( n\pi \right)-33 \right) \)​ 
My approximation formula yields the correct values up to n=31, I believe. However, the real values become larger than the approximation formula for larger _n_.

But for reasonable size _n_, the approximation formula is 99.9% accurate.

For example, for _n_=900,
\( \frac{1}{16}\left( 62\left( 900 \right)^{2}-56\left( 900 \right)-4\cos \left( \frac{\left( 900 \right)\pi }{2} \right)+21\cos \left( \left( 900 \right)\pi \right)-33 \right)=\text{3135599} \)
and Mathematica spat out 1.420456649789211*10^3137815, (thus 3137815)., but 

\( \frac{\text{3135599}}{\text{3137815}}\times 100=99.92937761... \)%.​ 
I'm not sure how useful the rate of change is, but we have a formula for it now, and those who don't have sophisticated computers can at least have a good approximation for even very large values of _n_.

Although what I am about to say may not be true, maybe somehow the rate of change and the God's number sequences are related somehow. Speaking of which, although I have been told that this formula most likely gives values higher than what God's number is, here is a formula I made! (For entertainment purposes only.)

\( 3n^{2}-2n\sin ^{2}\left( \frac{n\pi }{2} \right)-1 \)
[Link]
{0,11,20,47,64,107,132,191,224,299,340,431,480,587,644,...}​


----------



## Christopher Mowla (Oct 1, 2011)

I took the derivative on my Ti-89 Titanium Calculator and did more simplification myself. This is a much shorter formula for the actual rate of change of the formula for the number of permutations of the regular nxnxn cube. I made an effort to keep the original factorials from _f_ (n) as well. Perhaps if someone studies this formula enough, we can come up with an explanation how the rate of change works on the nxnxn cube. [Link]

\( {f}'\left( n \right)=\frac{\left( 8!\times 3^{7} \right)\left( 12!\times 2^{10} \right)24!^{\frac{1}{4}\left( \left( n+1 \right)\left( n-3 \right)+3\cos ^{2}\left( \frac{n\pi }{2} \right) \right)}\ln \left( 24!^{4\left( n-1 \right)}4!^{-24\left( n-2 \right)} \right)}{{}} \)
\( \text{ }8\left( 24\times 12!\times 2^{10} \right)^{\cos ^{2}\left( \frac{n\pi }{2} \right)}4!^{\frac{3}{2}\left( \left( n-1 \right)\left( n-3 \right)+\cos ^{2}\left( \frac{n\pi }{2} \right) \right)} \)​ 
and
\( \cos ^{2}\left( \frac{n\pi }{2} \right)=\left( n+1 \right)\bmod 2=(n+1)-2\left\lfloor \frac{n+1}{2} \right\rfloor \).​ ​(Note that this version of the first derivative of _f_ (n) has been simplified AND has been additionally simplified for n being a positive integer).​ 
With this version of the derivative, I was able to successfully compute n = 5 000. 

\( {f}'\left( 5\text{ 000} \right)=4.809141984700355\times 10^{96\text{ }928\text{ }416} \).


My approximation formula, yielded 96 857 499. So the percent error even at this size _n_ is ​ 
\( \left( 1-\frac{96\text{ 857 499}}{\text{96 928 416}} \right)\times 100=0.073164303 \)%.


Not that it's important, but if someone has a better computer than I have, could you compute _very_ large values for _n_ and post the results. Any results from cube sizes in the millions (or larger) would be interesting to see.



EDIT:
We can rewrite the derivative as [Link]
\( {f}'\left( n \right)=\frac{\left( 8!\times 3^{7} \right)\left( 12!\times 2^{10} \right)\left( 24! \right)^{\frac{1}{4}\left( n+1 \right)\left( n-3 \right)}\ln \left( 24!^{4\left( n-1 \right)}4!^{-24\left( n-2 \right)} \right)}{8\left( 4! \right)^{\frac{3}{2}\left( n-1 \right)\left( n-3 \right)}} \)\( \times \left( \frac{\left( 24! \right)^{\frac{3}{4}}}{24\times 4!^{\frac{3}{2}}\times 12!\times 2^{10}} \right)^{\cos ^{2}\left( \frac{n\pi }{2} \right)} \)
, where the portion raised to \( \cos ^{2}\left( \frac{n\pi }{2} \right)=\left( n+1 \right)\bmod 2 \) is an extra factor (approximately 505) for even cubes.​


----------



## mrCage (Nov 13, 2012)

Hi,

*Bump warning!!!!!!*

I made a simple script for calculating permutations on nxnxn cubes of various sizes.

Here is an example with size=6.

http://fmc.mustcube.net/Cube_Permutations.php?size=6

Obviously you just change the size parameter in the querystring for other sizes. If the size is missing it will default to 3 

Per

PS! I modified the code to no longer be using querystring, but session variables. As a downside direct linking to a calculation of other sizes than 3 (default) is no longer possible. The original version was simply too easy to "hack" and was prone to errrors for that reason ...

Actually you can link directly like so: http://fmc.mustcube.net/Cube_Permutations_middle.php?size=6


----------



## WBCube (Nov 13, 2012)

mrCage said:


> Here is an example with size=6.
> 
> http://fmc.mustcube.net/Cube_Permutations.php?size=6



I'm getting a 404, for other sizes too


----------



## ben1996123 (Nov 13, 2012)

WBCube said:


> I'm getting a 404, for other sizes too



I'm not. Nice script, works for really large sizes too.

100x100:



Spoiler



2,349,101,957,761,797,868,952,925,641,602,220,615,518,319,180,193,329,787,833,777,653,702,207,410,937,277,791,071,529,182,762,920,683,388,903,700,454,405,789,685,234,946,263,433,213,191,145,262,426,158,281,906,424,990,965,931,516,522,563,165,919,882,250,815,149,336,386,541,626,469,975,402,465,504,542,082,315,400,097,193,596,293,116,787,808,061,860,988,621,929,079,793,522,381,009,333,440,576,078,533,105,931,592,596,793,118,329,302,535,280,247,465,345,394,216,320,207,877,326,942,296,737,595,753,720,846,600,969,236,923,593,279,656,689,960,317,586,452,325,818,382,860,163,584,041,078,048,326,547,325,262,535,565,428,610,566,633,159,692,060,446,027,510,448,879,580,907,832,820,402,561,087,771,813,598,877,842,262,191,454,203,637,548,073,649,046,448,280,910,299,928,357,369,772,230,337,874,496,582,405,469,613,615,559,928,875,848,787,333,659,166,334,968,654,315,255,828,368,454,770,436,083,097,238,776,394,582,050,811,995,829,977,415,522,191,670,261,004,722,647,260,273,226,933,907,297,050,116,143,184,456,629,351,867,792,039,959,689,102,002,333,534,646,047,750,033,183,832,430,845,380,855,339,243,034,776,713,252,151,987,864,231,555,179,162,118,546,827,892,945,690,359,099,934,527,419,311,939,983,403,412,809,282,692,814,584,249,134,798,063,764,271,667,585,706,802,506,893,386,035,936,630,957,182,087,740,987,519,692,208,474,660,669,913,310,747,942,944,929,706,264,332,812,616,782,100,373,731,148,078,761,918,344,324,833,378,207,477,597,794,205,589,247,642,095,293,441,882,172,133,977,756,432,189,698,957,410,105,097,693,655,407,119,821,389,042,762,902,927,145,869,235,319,793,055,517,451,897,092,415,431,731,055,014,984,135,280,534,187,613,014,169,015,827,750,643,648,893,114,148,948,971,334,284,018,688,212,073,787,819,566,730,684,863,054,372,265,426,318,978,218,540,064,611,421,759,364,056,819,938,065,643,351,785,483,499,099,816,736,011,587,853,239,746,347,342,367,480,664,178,849,002,926,048,922,399,449,395,818,734,623,485,048,580,169,619,386,476,329,233,794,504,419,815,014,479,304,836,061,928,168,671,981,292,763,137,823,987,549,049,258,475,200,543,192,788,405,755,471,449,769,226,992,053,175,000,645,245,562,681,261,609,007,031,969,051,516,581,726,719,199,854,255,278,446,101,882,880,635,150,062,523,340,714,239,387,645,897,778,542,909,026,011,060,530,744,611,249,834,674,241,350,747,564,326,049,977,151,228,161,450,228,821,540,301,518,305,613,157,586,508,045,740,235,999,309,157,535,535,638,131,139,024,203,092,284,038,457,165,606,543,862,687,549,699,853,065,734,956,809,497,062,622,088,843,937,859,777,976,536,092,415,784,011,498,086,912,034,297,103,241,959,769,903,072,575,355,621,687,449,212,765,277,713,098,856,395,005,826,827,680,344,550,663,073,522,683,549,597,549,055,629,498,036,985,136,870,264,346,785,361,949,809,492,642,026,621,578,818,489,972,007,781,567,927,361,727,782,932,069,429,312,938,717,556,546,965,920,571,622,438,366,445,007,223,868,476,506,683,280,344,613,736,763,336,981,136,983,924,286,276,142,144,938,104,259,476,175,392,087,214,891,974,979,190,427,858,586,338,761,957,867,156,565,666,176,944,516,307,661,274,652,438,386,937,102,578,920,747,538,717,201,597,027,155,437,116,825,211,530,571,441,515,287,688,508,383,032,592,744,145,229,125,284,536,761,623,183,565,140,567,166,231,738,369,891,192,314,063,498,548,836,691,462,133,269,295,071,953,195,741,557,382,017,247,636,477,710,686,296,788,505,331,325,139,684,479,206,075,253,270,423,149,550,232,191,620,983,582,624,632,191,635,251,339,684,359,182,357,777,878,411,461,029,979,318,607,506,595,319,622,655,982,848,485,855,257,333,214,993,772,233,663,798,968,955,024,524,188,834,887,260,836,145,082,132,358,013,566,994,161,820,164,247,552,561,810,683,008,035,687,030,164,036,367,688,453,918,030,555,107,016,906,838,265,307,915,695,150,505,091,384,739,286,150,606,666,537,292,747,131,213,432,706,783,159,418,138,729,595,672,790,834,999,898,538,454,751,545,479,481,609,280,823,531,490,517,251,025,201,148,873,923,020,991,289,279,385,269,737,894,663,295,367,447,662,830,228,072,284,137,652,545,721,039,139,239,613,069,294,987,991,442,564,072,056,582,750,840,756,427,881,435,044,400,854,754,833,243,159,495,454,895,291,575,450,742,826,888,600,839,126,956,769,998,830,911,622,653,251,420,682,997,813,434,967,962,907,009,157,129,794,181,321,391,963,557,638,641,236,310,332,220,865,177,764,579,404,936,405,014,739,203,613,986,557,105,594,824,224,112,455,322,425,698,684,181,147,530,140,115,639,808,729,636,951,036,105,658,981,624,322,875,879,628,398,800,345,800,506,510,304,057,848,601,732,757,924,449,919,401,417,023,585,235,739,909,691,236,141,145,543,965,660,868,960,788,996,503,763,563,956,070,811,969,114,923,264,207,713,364,411,228,905,103,650,270,348,614,035,709,698,928,063,925,103,098,968,413,231,824,213,012,941,519,614,172,898,883,955,797,308,944,986,913,191,932,560,929,080,227,454,619,675,890,355,672,793,453,111,439,312,272,501,938,115,562,194,953,714,208,457,003,057,671,364,867,636,064,949,356,657,430,247,197,092,266,496,729,943,529,463,450,118,493,837,177,412,223,307,702,859,012,688,634,670,853,152,536,245,252,790,706,486,327,450,467,797,217,916,499,479,631,568,261,390,043,770,587,621,275,271,503,040,822,517,923,067,760,066,652,447,252,559,599,455,280,852,659,197,435,504,135,221,395,988,000,625,965,649,890,724,843,444,292,714,017,834,751,972,836,580,255,913,338,080,628,685,837,198,797,823,231,547,608,673,529,306,765,872,653,670,398,759,839,027,930,022,086,099,329,387,979,023,784,375,629,852,247,257,275,649,308,129,072,156,187,000,616,250,372,055,150,840,116,227,025,476,829,480,491,289,295,946,843,471,215,123,993,415,113,256,385,905,203,140,812,157,925,193,058,186,397,255,179,283,396,615,950,789,968,912,912,895,893,142,088,758,379,597,755,047,398,814,041,113,691,933,727,300,845,728,533,045,327,345,420,858,699,274,798,732,191,138,343,147,837,746,828,143,163,359,872,235,457,701,413,790,373,821,241,700,984,329,454,661,747,639,428,491,929,167,228,893,394,048,742,184,396,423,958,718,835,406,381,337,586,741,228,381,560,333,618,770,602,502,046,993,693,501,866,157,316,859,516,074,365,919,979,781,296,949,693,849,686,476,798,618,044,125,838,967,483,890,457,975,846,446,967,449,780,987,974,623,789,530,128,058,390,737,651,766,986,987,411,799,420,703,190,948,638,286,212,217,860,059,271,230,809,331,194,577,838,436,267,628,875,711,113,704,334,275,203,124,433,462,513,829,785,158,525,046,484,223,797,131,924,870,459,024,811,960,506,459,138,008,014,978,519,350,230,069,359,643,480,155,805,002,752,975,708,028,636,425,208,957,274,850,284,677,758,268,046,060,556,222,651,600,421,868,005,056,511,466,824,995,264,379,887,031,603,096,716,716,914,225,743,324,165,875,897,608,491,312,018,412,663,535,803,734,757,292,558,896,462,182,561,554,625,128,702,921,406,884,230,895,135,741,075,356,162,542,245,452,816,476,905,166,560,206,603,482,673,742,614,377,167,099,993,064,794,400,125,169,355,020,957,572,958,109,098,751,738,653,691,453,571,720,904,857,309,874,644,895,906,022,204,093,020,387,387,736,507,155,532,227,134,740,619,913,899,344,657,438,307,289,458,220,142,180,389,745,193,077,604,841,382,944,825,697,595,409,965,272,497,065,504,140,706,458,777,442,411,965,669,245,565,001,365,273,331,478,833,945,358,990,991,027,415,932,306,780,522,217,242,040,566,971,518,288,349,795,532,295,394,905,930,547,162,446,843,560,393,539,289,740,025,950,886,147,246,837,679,620,346,835,846,133,226,858,750,311,946,426,474,730,889,751,236,506,315,331,486,852,349,507,774,591,135,535,160,552,879,223,190,056,453,083,783,525,553,505,803,905,989,862,272,925,477,611,220,439,489,902,030,896,844,237,268,630,426,188,364,446,902,855,085,035,125,951,815,982,398,481,433,400,937,411,231,672,165,807,678,880,622,538,039,788,728,497,072,313,628,974,688,249,222,627,404,466,915,895,716,099,351,195,605,030,560,913,068,449,591,306,227,931,319,104,342,519,620,908,053,166,912,538,695,070,527,488,492,417,632,218,727,275,587,547,508,293,389,266,110,806,961,737,599,515,589,306,427,840,283,609,665,895,515,111,823,956,976,163,977,615,730,282,697,223,961,369,948,778,855,213,289,971,314,388,875,544,194,329,136,163,362,802,020,670,559,418,106,026,396,558,211,488,190,469,553,328,979,015,837,586,112,813,452,641,825,253,650,815,054,679,817,481,939,221,278,045,829,414,966,523,236,277,926,478,769,293,778,676,773,500,927,566,436,555,285,721,622,304,746,783,888,995,851,616,319,417,933,170,548,537,757,123,364,070,100,954,287,539,567,739,645,410,300,106,744,569,118,493,378,066,678,242,400,646,349,757,874,548,043,817,537,749,662,084,645,295,626,949,193,101,215,307,409,800,842,637,393,704,191,712,433,524,384,183,796,440,168,858,204,897,536,629,227,261,629,192,729,803,875,733,447,204,621,010,049,616,665,515,924,953,524,250,052,695,529,465,668,915,668,583,452,004,841,714,154,540,406,157,483,666,344,115,971,069,670,727,663,925,907,475,540,194,885,975,668,601,573,646,797,809,171,861,768,392,374,831,676,999,939,772,937,597,844,265,683,995,740,717,319,032,568,845,144,148,043,379,792,381,901,110,014,651,169,075,002,532,669,590,459,949,127,042,332,678,305,840,991,625,503,917,849,206,983,122,245,345,294,994,539,063,509,298,208,812,313,766,300,615,816,062,461,406,227,878,894,616,421,275,190,315,674,475,518,370,879,009,153,075,981,593,317,291,436,548,907,952,291,670,930,196,533,551,242,202,855,391,248,543,067,580,416,537,933,067,207,065,043,612,959,393,828,757,379,076,387,308,800,473,741,985,594,749,502,933,637,519,289,024,169,104,353,740,743,860,644,045,825,403,531,450,749,947,422,862,267,515,224,447,691,521,529,207,859,046,305,761,185,063,462,139,756,188,634,069,644,032,996,758,398,939,794,603,186,847,820,765,396,569,535,578,428,479,198,663,825,868,081,492,167,140,782,297,326,289,860,252,739,399,068,310,758,766,149,119,700,418,109,472,536,520,186,138,646,834,823,020,837,323,420,655,168,790,814,502,500,437,089,083,921,352,118,133,613,440,482,394,762,554,343,802,548,914,025,071,601,018,039,430,996,192,305,971,818,388,582,649,027,261,790,145,780,953,173,777,147,166,078,640,879,943,090,243,877,395,348,839,510,917,571,329,756,180,800,640,665,802,505,930,139,710,304,164,553,397,975,447,168,190,952,576,218,432,028,980,965,851,087,817,812,800,267,313,705,568,299,112,773,279,323,050,782,918,883,333,534,999,706,960,397,723,047,907,925,620,117,571,116,133,661,821,723,240,085,044,634,136,734,031,822,174,995,596,961,691,390,909,845,085,544,824,306,000,376,669,593,747,307,032,586,629,453,474,025,810,001,061,022,617,794,419,728,684,925,064,171,705,479,918,769,164,036,508,158,039,073,131,100,833,776,700,554,897,092,787,850,399,377,951,124,600,004,969,489,541,320,921,266,223,318,433,218,797,905,139,137,232,572,750,603,897,563,392,952,368,521,742,797,687,332,446,953,022,534,591,463,985,881,551,388,446,197,171,819,190,515,026,936,600,360,728,650,668,866,841,217,667,209,370,932,864,384,159,577,441,533,083,546,330,646,522,814,918,502,583,670,061,237,115,179,544,814,952,757,288,754,464,117,076,574,770,954,970,055,490,516,385,968,279,634,073,861,634,058,034,191,589,912,347,116,924,255,691,228,998,775,197,061,349,450,917,945,317,706,168,648,585,159,867,229,859,684,792,171,361,089,506,292,375,272,493,257,741,741,756,721,058,954,533,484,387,616,354,364,237,429,998,786,847,227,599,752,546,719,014,979,206,607,004,744,949,054,671,187,090,131,799,368,604,104,010,054,659,044,623,073,902,435,899,018,014,725,976,971,279,011,453,115,878,850,053,808,670,795,559,816,904,899,365,449,318,603,477,435,226,406,030,761,776,550,593,711,913,574,012,924,353,075,737,905,450,348,368,611,631,728,681,822,827,975,419,505,364,604,175,211,034,374,954,397,723,394,213,799,718,032,177,935,344,419,120,317,406,111,765,750,663,636,522,412,594,472,905,472,881,327,356,136,187,116,945,198,287,461,629,690,187,657,116,999,959,830,046,619,013,716,626,480,540,399,403,509,985,644,418,740,186,133,504,563,235,168,571,194,141,845,281,927,371,693,790,264,090,462,494,077,226,248,749,546,599,896,218,718,148,968,677,718,627,514,689,899,356,612,158,633,394,719,685,928,876,242,171,377,161,287,540,657,014,902,206,893,400,805,608,380,333,797,663,150,754,034,430,805,216,048,625,173,657,470,071,380,732,368,170,626,177,128,662,890,779,706,882,456,087,919,150,623,146,338,427,820,473,440,617,296,700,199,337,028,797,867,034,409,198,479,034,637,763,092,447,654,770,463,996,766,627,514,846,001,887,527,443,248,454,324,498,508,186,226,101,121,781,482,334,461,772,123,832,876,386,215,163,129,551,627,626,410,439,886,794,646,733,242,247,351,448,904,937,276,281,760,922,066,530,114,291,137,303,832,434,245,597,538,910,962,564,711,502,688,495,795,022,098,148,736,730,453,598,170,306,796,318,777,343,620,573,096,284,025,161,583,007,364,236,509,945,336,922,981,508,612,372,134,189,341,220,122,800,072,040,565,186,357,749,340,441,079,843,016,553,526,547,169,379,667,271,869,412,236,808,300,023,316,144,460,859,030,900,397,070,608,742,332,819,545,272,736,013,970,306,030,963,098,191,191,094,645,564,933,549,211,788,502,103,312,590,458,880,620,110,214,665,402,143,812,451,344,216,577,703,494,148,610,229,023,037,302,339,469,598,775,958,492,027,654,704,553,229,251,386,405,282,023,188,779,385,363,915,484,819,934,629,701,043,410,611,863,652,458,289,679,467,071,133,082,482,183,610,656,822,763,204,483,800,473,723,307,591,861,013,316,774,370,115,929,461,658,744,858,950,539,725,032,838,086,035,257,215,269,003,628,109,130,940,345,021,685,682,164,801,520,475,263,334,044,593,052,213,476,455,016,565,702,481,750,086,893,660,509,451,992,247,526,771,369,378,918,441,621,104,245,989,265,671,122,252,978,687,476,877,484,693,204,010,526,753,076,881,794,807,281,174,203,475,153,728,543,028,673,426,375,707,414,381,454,673,289,009,668,575,382,263,310,008,504,641,713,296,861,086,663,460,891,025,597,321,412,216,395,692,935,731,792,028,708,965,842,053,938,967,386,747,913,505,419,384,914,415,890,192,057,729,791,017,879,845,444,224,953,278,197,019,134,202,696,428,590,810,724,188,594,299,100,126,422,687,235,179,199,622,963,432,957,024,508,844,195,972,948,250,135,532,667,141,414,883,750,329,081,851,833,613,504,540,766,552,053,000,650,359,467,079,766,295,388,529,903,350,806,137,159,869,478,474,801,081,725,280,530,016,269,313,802,054,868,063,623,331,836,116,197,462,719,885,316,085,903,130,358,494,342,545,340,064,308,555,713,272,647,701,987,641,619,875,079,380,434,732,555,435,640,309,373,673,949,156,455,525,526,692,544,123,885,265,236,931,564,663,883,005,508,826,919,980,302,965,893,639,406,885,265,784,914,456,121,879,481,379,484,790,283,997,576,188,668,602,081,042,028,829,135,503,408,635,399,993,166,375,207,249,072,974,895,739,635,373,376,616,750,041,444,383,991,846,500,990,560,726,281,588,305,306,881,668,210,267,264,530,420,722,571,692,417,474,888,663,330,995,347,135,090,511,154,483,042,362,599,554,127,387,313,186,758,463,012,237,598,857,275,026,485,089,404,066,246,590,306,699,959,198,324,417,820,306,742,798,593,696,684,864,106,856,407,516,778,543,190,004,542,623,120,490,329,550,143,964,280,618,382,166,932,222,653,205,667,924,413,455,326,310,146,074,645,839,327,012,721,825,504,945,305,184,812,593,699,414,554,218,248,579,494,890,522,564,595,649,327,779,340,838,071,475,838,514,174,744,933,878,763,357,071,942,694,357,594,870,804,319,518,767,730,513,110,344,893,485,339,732,595,161,072,727,345,800,162,262,275,246,689,353,800,741,292,338,215,995,022,604,139,993,699,229,144,961,116,407,407,734,658,729,819,285,366,175,241,489,812,415,681,279,199,793,978,186,584,136,694,415,957,736,438,658,209,874,420,732,119,948,473,857,686,056,397,746,539,983,780,307,184,309,498,659,155,241,834,092,109,712,813,846,944,273,422,558,643,645,906,274,808,673,972,341,295,724,368,831,152,306,053,082,301,614,636,356,734,818,604,129,703,267,485,297,040,117,598,284,042,738,065,120,910,705,747,612,803,709,435,891,000,990,480,577,784,180,375,497,910,275,785,794,334,012,893,839,476,577,788,861,481,590,765,184,420,831,447,153,764,108,175,210,577,783,114,137,456,705,828,241,303,527,685,179,665,954,467,533,278,243,398,944,213,122,244,445,974,124,819,806,417,446,276,968,585,770,185,040,757,215,517,757,377,690,134,727,394,965,120,248,904,826,515,728,101,050,809,082,756,955,242,314,401,668,613,075,869,092,055,633,856,650,918,266,519,460,781,593,571,949,409,547,736,902,154,990,428,011,067,503,989,557,822,716,771,872,204,591,999,695,594,994,696,410,583,801,703,564,420,474,600,274,219,631,516,721,181,039,692,803,267,119,178,916,851,675,696,158,404,461,921,353,904,039,229,159,568,375,105,900,446,115,162,383,440,591,042,240,155,301,379,702,280,722,090,134,493,323,526,897,832,064,242,149,000,313,797,377,201,509,452,339,106,515,444,350,374,868,173,529,642,890,041,708,231,952,816,001,856,458,818,100,895,542,814,131,394,227,915,301,049,241,685,496,612,594,338,031,896,995,636,019,915,680,357,756,500,973,741,726,312,726,254,226,056,791,498,834,528,712,240,292,664,536,768,643,528,938,145,852,025,141,995,533,346,038,221,243,422,082,083,389,765,854,930,595,717,818,758,906,790,667,026,833,375,490,109,618,421,628,857,871,516,167,964,814,181,911,260,620,083,814,296,488,064,264,736,800,079,013,375,265,816,753,270,857,708,388,617,190,891,518,489,584,844,691,105,786,932,348,454,723,751,884,947,471,177,865,934,463,213,462,400,706,223,637,792,262,815,141,299,552,004,982,416,652,996,389,176,918,739,141,390,009,253,959,748,208,753,860,294,496,824,117,854,414,534,440,215,447,117,909,173,599,110,868,969,881,059,138,917,114,421,508,152,239,808,538,878,382,638,062,733,689,673,895,231,948,285,966,160,995,087,895,480,432,658,026,261,214,770,534,752,932,105,850,895,593,914,905,055,060,405,033,486,540,832,276,849,226,822,538,447,371,057,516,502,018,016,896,120,896,132,267,500,164,020,989,435,539,497,490,605,497,674,029,002,481,994,832,481,071,648,792,466,121,188,546,905,663,327,246,042,194,726,237,257,304,171,197,125,276,635,201,253,996,076,147,046,355,559,700,052,153,993,109,591,299,169,515,158,198,066,739,402,412,960,718,079,302,927,668,534,319,047,589,304,370,119,149,612,065,556,346,823,600,845,353,009,852,994,715,959,834,862,351,326,170,289,738,884,651,101,954,300,446,682,111,280,526,274,826,969,305,088,492,701,360,539,463,278,372,107,710,455,786,837,488,890,913,935,931,658,282,190,907,579,950,980,469,385,998,135,018,068,319,411,086,690,307,035,545,242,572,278,377,766,633,105,346,796,613,031,687,521,042,109,489,079,947,588,864,949,527,874,793,573,700,100,112,708,614,800,438,954,886,293,836,616,729,751,916,847,413,856,690,125,894,640,647,238,797,508,517,676,813,603,006,563,189,750,888,701,509,980,389,338,478,427,682,477,328,084,433,228,062,892,679,046,558,337,547,883,019,590,639,371,473,216,926,810,663,064,429,901,009,051,838,299,429,900,352,823,372,006,882,237,908,443,027,097,075,645,848,815,861,282,540,330,429,513,642,108,025,051,557,455,604,457,270,771,280,767,500,600,966,318,982,221,404,298,334,433,321,223,084,455,407,940,833,169,064,103,026,386,383,922,475,990,958,888,908,419,015,923,390,681,817,465,062,300,640,201,168,331,432,924,087,563,004,866,245,537,062,093,392,461,535,414,397,133,011,494,021,452,921,904,758,887,188,318,503,174,644,298,998,564,557,512,093,156,523,712,131,962,959,810,450,514,685,280,599,512,510,803,980,456,738,920,328,190,318,108,879,113,319,263,142,480,306,959,599,552,980,383,751,774,542,517,911,469,208,327,080,482,705,264,581,469,549,024,480,136,312,398,325,753,688,748,484,359,256,521,637,685,928,330,331,510,551,017,887,569,618,758,327,395,669,263,396,717,635,564,901,927,577,424,804,250,846,173,972,675,047,632,196,757,930,927,790,171,625,827,240,034,986,074,349,681,044,135,364,683,262,278,759,447,660,200,885,702,509,580,018,857,784,881,088,732,277,885,136,884,471,419,408,291,096,739,193,153,815,914,461,247,174,263,161,386,882,013,711,656,307,313,037,545,058,571,101,070,548,233,993,777,330,101,762,096,115,863,761,633,420,034,104,634,219,810,922,209,035,585,105,290,251,205,521,449,421,391,924,638,154,419,652,004,929,020,776,321,949,541,594,264,392,778,269,402,684,881,011,867,893,936,211,977,037,935,139,597,700,125,292,961,959,484,895,333,447,582,176,409,460,843,090,493,088,513,222,996,156,737,023,254,732,382,629,178,717,888,484,357,744,716,969,814,673,082,722,489,543,692,945,751,818,501,220,543,747,995,724,017,024,332,565,864,231,011,504,418,489,107,036,876,986,436,300,211,791,028,103,039,911,363,478,768,945,389,464,450,359,554,130,568,087,662,552,517,530,308,414,527,792,317,333,292,704,302,150,884,259,536,923,412,895,733,916,749,288,560,316,760,327,575,884,169,538,930,283,716,299,476,456,533,539,962,156,847,839,728,826,979,314,322,415,925,314,778,354,699,488,751,038,240,667,215,952,551,498,438,454,574,245,237,699,657,216,333,947,273,688,604,561,580,286,295,452,938,653,489,394,991,031,140,484,016,771,519,302,532,290,242,319,667,326,908,387,637,644,988,538,269,608,238,648,122,808,017,109,730,488,953,912,417,090,441,633,576,799,703,209,376,014,119,956,715,613,780,379,849,325,251,619,259,770,914,829,789,329,852,310,829,059,856,787,152,412,815,480,359,920,474,538,092,333,770,681,007,111,630,940,410,728,042,747,919,967,448,945,522,867,741,365,377,122,414,569,326,193,374,514,857,681,178,340,653,367,264,521,140,804,794,680,232,896,260,228,801,390,105,383,145,989,306,669,210,740,302,357,862,653,867,107,560,877,499,805,956,106,744,343,340,383,568,475,263,241,011,013,537,263,505,535,568,969,912,841,208,717,187,814,398,009,309,808,931,563,106,389,000,254,386,517,197,898,552,779,947,775,187,495,442,541,035,425,287,741,084,583,805,068,063,867,722,945,347,883,791,709,197,114,281,835,603,625,594,152,123,377,575,953,438,199,520,115,622,387,981,838,272,752,795,329,033,125,908,395,698,416,788,157,336,939,319,383,131,841,959,051,819,400,425,692,432,806,599,914,234,541,914,840,053,196,583,344,621,291,579,911,969,307,598,556,745,256,707,500,414,612,387,951,742,173,807,791,626,782,956,878,368,464,099,443,137,539,186,399,694,663,963,201,463,923,359,204,342,011,966,628,164,715,597,806,498,283,282,783,616,416,690,555,092,887,260,589,106,599,371,333,981,973,008,951,472,149,379,230,421,922,408,707,136,505,873,483,567,806,461,074,265,237,585,697,664,229,845,185,656,144,241,573,334,316,790,615,577,016,890,146,727,665,682,878,236,992,517,241,543,410,644,232,305,738,300,106,443,763,867,009,929,125,829,916,710,693,159,160,053,389,077,092,542,717,251,711,616,136,772,303,004,624,661,971,643,939,381,536,292,573,470,223,907,553,076,981,999,929,105,066,133,558,750,006,004,863,730,102,618,573,379,966,986,963,742,459,993,440,471,647,212,422,919,331,490,448,855,581,424,128,492,319,439,379,650,691,158,000,942,440,929,721,978,358,871,673,267,328,106,092,416,004,794,333,914,447,232,827,789,330,764,216,824,539,964,505,362,197,302,933,599,137,946,600,962,103,053,601,814,620,093,057,339,281,344,361,042,048,569,531,193,848,878,385,767,000,110,278,062,719,963,627,018,779,036,531,390,640,550,941,834,670,843,654,126,638,210,026,659,167,857,823,655,147,237,892,996,159,538,732,558,680,008,191,242,799,200,857,367,827,554,133,649,687,159,827,206,550,775,220,334,922,577,648,643,647,793,302,113,332,120,824,119,959,192,115,130,990,766,532,284,882,880,249,239,767,910,278,088,824,517,213,316,256,761,619,480,241,015,666,697,138,229,735,437,922,933,302,913,959,682,882,568,166,218,095,185,360,478,478,121,977,638,056,808,662,508,689,499,603,967,294,795,670,404,920,308,791,073,187,690,971,580,030,925,830,165,488,796,149,509,040,124,302,014,701,761,622,673,369,307,217,950,349,983,961,932,494,785,719,962,364,670,610,249,892,094,402,635,143,287,846,736,938,862,215,557,001,810,884,208,754,774,705,972,941,903,826,804,314,273,729,087,855,422,491,464,378,351,622,363,038,982,597,731,674,673,891,522,550,128,319,327,187,527,482,502,533,913,297,579,974,232,180,068,198,415,128,285,746,870,586,141,641,916,892,456,636,576,070,309,701,323,936,873,322,903,525,034,812,053,747,935,649,698,285,340,237,064,579,258,610,460,997,806,936,621,149,726,903,272,090,120,632,673,194,467,355,985,761,318,131,717,417,588,460,700,397,201,105,841,207,789,573,127,100,208,920,963,248,524,575,644,773,492,163,466,238,081,134,262,198,174,620,915,410,705,063,731,059,448,814,728,711,850,854,654,755,796,665,112,852,152,794,332,489,921,303,100,052,666,536,945,329,024,075,760,486,728,081,770,481,265,895,332,917,363,541,794,708,386,131,716,489,780,474,951,586,356,557,129,341,811,754,291,184,804,176,743,780,717,668,411,723,318,524,055,634,398,129,536,780,745,786,617,479,638,205,327,774,527,417,967,016,050,558,029,706,184,460,931,258,536,894,398,205,324,039,482,628,820,514,550,768,329,944,536,980,537,224,116,384,426,400,813,796,950,998,938,176,514,722,803,264,947,123,503,551,108,750,635,685,553,144,982,108,279,384,980,566,248,499,692,356,624,917,965,711,747,434,554,681,424,699,252,981,759,307,891,680,391,658,288,928,756,793,162,009,532,934,016,926,252,776,726,276,408,794,449,804,994,773,669,936,442,756,882,014,427,695,826,263,415,804,988,172,105,442,054,464,519,141,801,653,501,342,596,752,603,317,705,330,242,545,308,988,389,421,159,201,802,534,071,323,432,621,580,681,787,225,101,262,393,631,045,083,606,615,821,355,610,515,869,343,798,315,544,403,386,218,204,195,494,957,747,207,162,642,742,657,368,226,341,112,355,888,615,376,734,933,577,776,583,299,025,733,874,006,325,616,149,392,555,386,144,804,237,676,455,303,619,258,750,184,554,124,583,385,658,589,577,791,147,462,656,510,395,666,568,225,115,228,643,320,970,019,266,605,721,183,284,605,900,700,939,564,583,884,023,442,164,213,123,332,973,675,491,827,935,889,636,102,238,258,886,155,603,100,903,698,023,185,512,964,528,306,803,082,248,667,128,500,023,839,646,078,817,847,929,355,211,880,485,921,644,659,257,900,173,540,948,824,712,906,600,843,102,503,762,835,451,141,305,985,049,270,775,668,485,844,133,531,289,053,618,075,731,197,767,091,436,082,020,336,308,613,233,095,257,160,085,468,426,519,936,606,729,322,153,337,018,829,166,512,093,579,069,028,752,575,811,093,118,967,483,232,889,985,364,607,938,070,413,688,069,291,661,626,126,715,144,336,226,724,283,617,339,921,888,167,545,984,081,869,965,092,084,247,832,540,245,160,096,557,673,434,573,476,882,605,854,046,279,976,257,836,433,953,046,186,835,755,289,803,976,758,470,017,523,764,673,738,611,341,107,531,678,588,974,561,848,148,681,465,766,880,474,807,230,282,549,518,612,070,114,152,661,001,060,036,965,411,979,251,921,126,316,549,094,350,071,212,107,334,149,603,825,722,753,683,812,474,699,800,087,416,372,897,908,409,221,713,474,794,797,148,059,453,275,682,417,269,155,275,583,431,177,205,392,114,120,359,284,596,883,078,510,225,397,913,551,525,412,694,264,379,808,595,408,351,132,859,087,652,064,717,373,213,551,209,183,533,491,011,141,868,920,454,438,111,844,442,534,154,681,453,465,300,982,684,154,772,896,755,762,490,542,209,460,695,928,050,081,519,015,677,347,472,680,521,027,817,524,301,811,983,413,441,178,210,029,066,286,851,682,560,423,841,024,641,138,649,826,068,340,523,612,114,880,371,194,000,949,478,985,837,761,302,231,354,951,379,257,627,987,853,062,406,362,238,319,631,594,497,540,976,398,748,426,359,887,515,833,993,770,296,785,462,699,274,495,832,483,715,426,617,254,904,121,476,950,390,777,390,100,715,124,705,388,558,633,971,503,892,178,140,585,533,508,780,446,376,998,273,644,737,683,102,488,443,980,716,689,909,062,300,038,422,035,426,592,469,520,083,510,648,848,301,655,975,687,557,952,452,859,511,091,581,609,923,519,302,106,584,671,722,242,080,405,083,068,183,359,636,397,368,565,743,416,017,880,796,816,603,799,187,085,972,932,209,319,573,853,872,539,000,653,634,530,152,583,449,239,628,375,448,938,869,503,368,533,436,200,612,607,646,010,100,603,537,460,098,560,982,675,595,458,076,372,148,153,514,163,621,898,921,140,849,171,716,669,401,968,916,055,995,415,913,931,532,082,763,718,888,067,518,213,098,988,437,901,692,770,541,010,939,559,753,658,313,925,997,791,889,400,962,795,772,670,292,789,964,605,771,908,151,716,782,110,471,472,069,334,028,489,821,022,499,825,699,105,437,396,992,351,602,040,878,756,804,238,940,433,745,054,443,664,976,132,517,340,127,270,659,752,449,934,045,710,966,347,979,725,604,647,493,258,942,423,442,361,850,113,396,590,336,417,295,482,280,869,319,141,571,214,658,363,926,927,061,039,793,153,148,351,556,241,209,709,909,875,586,594,362,557,614,048,433,545,603,540,305,232,761,536,781,737,428,562,648,141,601,173,024,936,897,522,656,844,016,849,430,091,990,821,440,774,200,493,989,010,076,902,244,682,277,775,177,473,751,084,811,344,240,414,030,505,276,492,993,284,303,032,650,873,569,536,098,138,658,119,097,292,669,990,370,807,295,504,349,737,009,395,184,309,042,683,260,847,578,233,379,330,978,365,620,839,916,259,270,123,356,498,713,119,682,421,211,616,754,565,697,565,778,171,515,502,173,431,529,032,368,736,285,906,167,522,031,502,433,457,996,981,061,490,073,778,961,940,941,156,895,570,335,426,858,251,890,273,056,094,806,599,243,654,372,768,223,718,492,656,864,335,291,674,334,936,049,562,726,995,946,634,987,683,978,724,523,643,743,850,526,876,219,598,341,419,837,887,952,715,573,533,983,274,961,770,785,276,438,716,485,834,646,687,838,430,769,353,880,525,843,994,213,027,191,667,664,222,617,844,986,562,004,899,211,671,521,716,306,602,453,299,966,057,945,924,035,350,234,126,546,088,619,582,358,202,850,974,710,547,944,351,927,308,655,830,115,258,316,259,763,808,169,329,045,216,961,526,650,853,419,741,364,436,921,253,253,232,178,695,561,934,798,966,245,661,686,959,570,926,113,439,945,594,271,675,886,141,295,179,318,521,244,941,952,631,721,975,998,111,902,197,803,303,816,912,298,886,052,579,717,982,001,973,421,665,288,435,994,258,405,984,342,525,862,595,235,094,765,200,186,552,672,039,439,920,651,963,678,185,743,345,440,370,270,187,261,134,571,505,542,929,348,171,842,320,726,792,832,472,029,908,461,786,454,082,099,507,300,065,268,972,475,496,593,304,951,456,894,196,821,621,180,228,703,343,903,202,515,449,970,254,801,565,481,213,434,820,256,686,336,700,893,035,762,511,566,769,937,778,556,812,307,329,436,630,764,578,321,912,442,024,078,185,569,756,960,328,785,371,253,360,222,901,438,827,456,045,345,364,194,508,836,889,951,008,855,274,217,377,062,194,634,469,820,149,366,400,375,662,029,553,503,431,093,473,253,964,102,492,615,010,367,234,806,303,643,258,607,497,904,292,041,085,820,682,009,246,908,978,572,145,030,808,157,807,917,078,485,727,898,978,037,672,542,743,927,228,969,331,440,781,141,312,788,127,330,503,514,545,131,697,419,982,573,324,674,991,704,888,129,994,704,666,740,892,128,401,304,355,923,163,225,274,502,749,579,442,576,382,508,767,754,082,757,991,554,557,411,673,199,200,648,676,578,981,469,072,271,624,804,718,482,115,015,673,300,006,737,309,404,468,653,541,949,594,024,640,541,454,646,299,933,103,733,517,367,275,968,106,891,587,414,201,979,210,108,360,495,250,937,286,568,634,754,220,268,615,371,176,405,807,930,391,927,422,386,242,353,662,966,105,876,667,734,749,738,520,158,832,223,347,391,413,764,375,417,830,208,203,288,715,143,262,839,323,666,156,753,510,689,477,762,423,824,258,064,280,869,562,802,814,690,056,228,124,688,596,673,250,368,364,326,369,324,375,465,815,825,548,978,366,722,949,594,135,377,328,451,214,413,183,923,795,930,382,819,985,474,684,612,809,879,244,926,935,759,673,765,338,532,292,164,931,011,667,814,317,445,562,282,859,049,804,039,862,414,770,231,413,447,455,451,062,170,338,801,325,695,006,902,308,881,787,476,704,756,266,773,160,788,519,245,478,198,754,535,829,034,699,315,891,255,417,980,122,708,249,396,232,321,355,372,338,589,268,577,313,631,052,221,744,214,751,331,197,612,556,380,565,567,430,036,002,115,515,074,610,219,184,017,322,915,141,573,621,820,963,430,530,369,769,666,794,188,609,957,161,219,446,400,640,600,631,189,787,445,754,432,400,675,368,497,294,522,368,469,852,294,159,940,769,552,120,459,641,224,943,490,695,813,963,536,289,644,606,318,116,094,933,170,241,834,896,864,038,403,538,320,420,727,968,536,529,776,940,388,879,285,600,904,152,310,505,755,517,119,606,533,723,184,664,790,345,187,928,510,375,813,260,908,563,912,685,949,469,456,837,930,505,779,454,255,876,193,591,396,138,974,444,743,443,822,541,113,564,953,364,563,391,601,470,817,724,732,921,108,752,187,249,265,435,836,251,692,512,479,866,949,612,004,195,866,709,981,595,961,271,225,153,199,836,939,604,555,413,153,183,004,521,521,847,150,277,248,113,243,695,070,253,746,753,594,191,789,832,160,160,498,191,560,613,279,154,003,240,845,863,790,444,386,643,054,017,083,689,289,215,623,106,101,715,454,233,331,858,942,097,921,524,715,736,071,379,963,747,236,524,528,591,808,932,197,224,242,564,185,216,071,778,412,085,525,929,048,168,820,464,839,470,775,564,255,227,767,190,313,199,045,778,629,892,518,382,806,063,395,838,063,966,944,616,448,435,777,769,158,295,178,934,283,802,806,159,172,720,861,221,848,535,772,310,254,120,008,055,902,976,447,715,800,151,033,307,943,245,685,083,826,644,975,535,789,546,365,605,907,702,822,427,007,231,537,301,138,308,007,063,794,553,781,808,087,322,658,050,410,617,211,652,209,279,646,696,159,900,478,609,632,129,552,284,553,547,147,719,712,784,536,488,261,136,045,759,342,849,326,858,283,138,194,225,834,497,934,765,903,920,506,252,274,614,324,231,465,530,715,329,159,410,650,129,598,829,610,074,495,702,707,058,214,073,840,118,241,733,715,729,211,370,331,386,295,419,535,027,619,875,708,294,596,725,486,529,448,737,305,016,618,907,162,474,797,252,195,379,430,640,111,961,185,020,055,226,344,729,525,044,601,051,237,185,951,283,078,402,474,395,494,608,390,340,679,335,044,301,471,314,709,030,512,413,044,350,108,572,516,560,796,716,459,248,256,232,003,304,583,581,735,437,610,847,639,872,839,798,241,435,683,993,019,597,435,661,699,202,566,313,803,336,928,774,787,973,902,049,770,655,130,547,077,362,805,839,386,094,064,418,018,082,247,295,872,168,240,517,451,011,075,344,956,751,307,223,978,824,772,432,709,613,454,252,908,397,091,695,119,134,151,358,999,308,726,087,866,668,854,988,576,449,264,979,096,519,270,366,963,869,928,537,156,646,152,866,972,486,169,785,599,220,173,015,427,158,785,523,884,187,101,584,171,498,081,323,105,648,491,574,053,862,784,975,333,773,936,733,017,047,842,992,446,154,156,303,911,486,892,915,773,113,890,065,688,370,892,528,939,754,251,809,637,341,226,953,165,641,088,971,351,216,134,412,374,197,474,832,178,045,722,221,681,025,886,603,572,468,929,189,126,447,885,426,269,459,115,599,456,335,349,149,989,918,473,454,990,367,515,584,518,144,705,042,294,805,178,786,713,771,871,353,563,466,497,542,312,890,678,469,535,826,475,980,984,324,106,263,481,329,260,717,086,842,166,474,389,033,412,536,450,500,888,766,518,443,484,378,580,288,638,702,684,198,192,784,941,274,498,771,561,074,547,865,966,105,869,377,123,856,698,479,189,532,913,289,054,409,615,215,813,589,937,240,696,082,833,454,693,309,115,257,912,123,266,954,747,048,594,892,714,244,320,483,016,734,220,948,784,742,843,887,778,838,095,667,601,440,762,919,252,722,569,820,432,118,191,464,932,232,259,173,501,837,382,548,391,621,500,314,592,181,385,494,369,552,666,352,667,470,941,146,068,233,575,479,712,411,027,994,373,435,229,667,499,040,301,458,401,273,984,879,287,559,693,630,986,055,136,301,119,533,029,847,614,506,044,041,434,741,866,111,624,332,975,910,844,864,341,980,045,187,865,017,546,376,748,315,263,051,536,553,433,841,811,593,116,949,068,555,556,584,932,853,450,425,952,550,200,088,246,110,972,046,414,712,706,753,647,859,726,887,058,787,805,907,727,266,511,104,246,597,789,259,997,510,080,547,392,797,230,365,157,596,712,731,832,117,199,709,433,458,335,505,549,191,378,213,441,616,133,042,773,742,230,411,677,164,858,761,196,613,907,873,433,981,314,101,697,233,654,081,314,489,218,924,021,691,638,852,455,837,868,082,958,040,415,181,075,203,579,636,264,679,771,332,491,165,841,326,225,730,020,088,329,238,206,653,170,531,814,298,642,510,142,932,235,989,683,762,034,940,856,153,582,905,491,576,347,865,193,588,789,666,673,727,381,878,922,182,767,471,744,280,436,914,920,156,563,238,818,681,069,687,096,062,447,055,222,182,871,733,267,565,880,242,240,481,913,985,026,316,708,691,231,881,205,100,022,844,135,505,026,107,774,707,109,926,312,428,662,886,483,735,581,458,235,946,022,265,189,458,997,608,735,735,588,828,116,934,026,508,032,946,295,893,150,675,693,123,276,982,829,458,114,200,308,885,451,360,828,937,276,681,680,545,990,458,920,269,717,898,311,354,810,629,550,998,711,111,443,798,973,032,302,879,131,688,177,865,457,813,544,906,064,780,978,340,360,460,327,196,917,163,651,580,827,497,212,036,377,055,213,055,447,775,472,135,611,005,023,285,895,180,970,839,994,446,510,961,468,753,971,768,552,046,350,829,957,122,478,230,549,438,748,163,045,595,308,899,980,490,020,155,422,705,976,366,296,529,718,324,698,335,125,850,218,058,394,019,616,305,690,566,092,168,626,273,541,714,051,195,574,709,765,111,148,483,406,257,924,340,570,304,117,882,016,820,474,866,934,550,012,089,235,474,700,231,917,377,605,714,219,873,762,035,890,583,943,079,391,843,804,851,442,898,801,537,554,241,309,439,196,455,484,403,758,009,205,053,329,168,683,879,963,547,120,403,848,583,483,738,250,483,917,291,053,415,895,355,561,165,740,394,380,644,707,976,986,601,285,999,347,448,078,311,867,955,869,196,091,779,515,913,472,359,235,600,795,193,265,759,746,436,188,471,185,911,689,761,625,783,859,168,950,968,266,696,576,343,630,024,039,882,018,548,320,529,823,240,226,771,488,577,709,475,866,596,442,893,545,280,758,154,848,736,049,097,375,998,063,336,297,998,122,143,853,589,609,121,447,651,470,843,484,154,116,820,824,980,237,877,655,845,060,003,600,942,712,807,991,526,831,831,282,859,235,790,595,849,625,963,050,221,746,433,211,260,822,767,544,907,655,384,384,034,568,368,720,210,890,165,861,703,896,635,532,834,508,754,292,093,469,689,392,778,233,102,627,787,685,643,961,345,800,634,974,425,589,565,417,440,695,584,794,552,780,664,477,270,243,916,678,155,367,517,952,832,224,856,730,775,107,529,405,500,935,550,981,108,598,246,437,544,762,494,921,473,965,842,669,542,603,148,584,207,882,106,572,658,782,188,722,817,157,293,740,636,192,380,648,431,406,709,282,147,756,252,112,163,730,649,146,072,575,468,855,650,436,918,054,350,776,534,197,943,512,014,444,437,422,360,631,384,166,056,695,995,874,695,859,660,782,845,860,969,755,404,907,884,416,717,703,196,288,689,724,445,205,270,978,668,300,714,262,835,360,815,868,978,018,272,449,374,661,294,358,263,116,259,525,302,865,706,655,236,347,314,703,927,704,886,480,811,422,246,767,689,996,229,741,807,770,857,523,868,629,294,768,189,037,126,811,133,260,202,539,746,729,502,830,591,642,177,327,757,626,977,569,791,799,130,294,099,023,223,289,764,899,706,655,956,236,690,563,046,135,068,275,100,243,617,767,233,966,977,045,801,691,356,181,039,553,414,727,770,580,928,692,801,303,452,186,214,830,052,732,280,716,013,440,491,616,927,063,272,632,316,705,590,796,844,093,322,943,266,816,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000


----------



## WBCube (Nov 13, 2012)

This is what I get: 
Shame


----------



## Godmil (Nov 13, 2012)

That's pretty cool, it's nice seeing just how quickly the number gets huge.


----------



## tim (Nov 13, 2012)

WBCube said:


> This is what I get: View attachment 2497
> Shame



You miss a ".php" at the end.


----------



## WBCube (Nov 13, 2012)

tim said:


> You miss a ".php" at the end.



Ah, thank you. Not sure why that was happening, I was just clicking the hyperlink.


----------



## mrCage (Nov 13, 2012)

Using the bcmath library in PHP is a lot of fun. It does maths on numbers represented as (long) strings. I made my own functions for exponeentiation and factorial to make it work


----------



## Stefan (Nov 13, 2012)

mrCage said:


> I made a simple script for calculating permutations on nxnxn cubes of various sizes.



Bet it's not simpler than in Python 
http://codepad.org/RCtDpfk0


----------



## Ranzha (Nov 14, 2012)

Stefan said:


> Bet it's not simpler than in Python
> http://codepad.org/RCtDpfk0



And Tweetable, too.


----------



## mrCage (Nov 14, 2012)

Stefan said:


> Bet it's not simpler than in Python
> http://codepad.org/RCtDpfk0



That was really compact!! But it has no user input and no output formatting. My code can actually group the digits in blocks of desired size and with chosen delimiter. For better readability 
I did not know that Python works "out of the box" with really huge numbers. Will it also do decimal number calculations like needed for pi or the golden ratio ??

Per

PS! My current hosting has a rather short script timeout limit that i cannot overcome. It is not allowed, because the hosting is not on a dedicated server ...


----------

