This problem is a programming version of Problem 151 from projecteuler.net
A printing shop runs batches (jobs) every week and each batch requires a sheet of special colour-proofing paper of size A.
Every Monday morning, the foreman opens a new envelope, containing a large sheet of the special paper with size A1.
He proceeds to cut it in half, thus getting two sheets of size A2. Then he cuts one of them in half to get two sheets of size A3 and so on until he obtains the A-size sheet needed for the first batch of the week.
All the unused sheets are placed back in the envelope.
At the beginning of each subsequent batch, he takes from the envelope one sheet of paper at random. If it is of size A, he uses it. If it is larger, he repeats the 'cut-in-half' procedure until he has what he needs and any remaining sheets are always placed back in the envelope.
Now let's assume that foreman suddenly collapsed and the other one came to the rescue. That means that the second foreman could start from some various configurations of envelope. Now, for each possible starting configuration of envelope print the expected number of times that the foreman beginning from this configuration finds a single sheet of paper in the envelope.
Input Format
The only line contains a single integer where A is the smallest needed size of sheet of paper.
Constraints
Output Format
For every possible configuration of envelope print the expected number of times that the foreman beginning from this configuration finds a single sheet of paper in the envelope. As the expected number may be represented as , output it modulo , i.e. . Follow the sample for format needed.
Sample Input
3
Sample Output
0 0 0: 0
0 0 1: 1
0 0 2: 1
0 1 0: 2
0 1 1: 500000005
1 0 0: 500000006
Explanation
If the second foreman starts with empty envelope they will obviously meet no single paper sheets.
When there are one A2 and one A3 sheet after one cut we stay with two A3-s with the probability and with a single A2 with the same probability . In the first case the number of meeting the single sheet is and in the second case it is . That gives us the average