My matrix multiplication travelogue

Computing the product of $n$ matrices $\mathbf{M}_1, \mathbf{M}_2, \cdots, \mathbf{M}_n$, that is $\mathbf{M}_1 \mathbf{M}_2 \cdots \mathbf{M}_n$, is tedious for a person and for a computer alike.

Here is a summary for anyone who is not used to matrices and their products. A matrix is a rectangular arrangement of numbers or symbols wrapped in parentheses. In this problem every entry of a matrix is an integer. For example, the following is a matrix.

$\begin{pmatrix} 2 & 0 & 1 & 6 \\ 0 & 5 & 2 & 8 \\ 1 & 4 & -1 & 7 \end{pmatrix}$

The numbers arranged in a matrix are called entries. A horizontal line of a matrix is called a row, and the rows are named row 1, row 2, row 3, ... from the top. A vertical line of a matrix is called a column, and the columns are named column 1, column 2, column 3, ... from the left. A matrix with $m$ rows and $n$ columns is an $m \times n$ matrix. The entry in row $i$ and column $j$ is the $(i, j)$ entry of the matrix, and the $(i, j)$ entry of a matrix $\mathbf{A}$ is written $A_{ij}$.

Just like multiplication of real numbers, matrix multiplication takes two matrices. When $\mathbf{A}$ is an $m \times n$ matrix and $\mathbf{B}$ is an $n \times p$ matrix, the product $\mathbf{AB}$ is defined as the $m \times p$ matrix whose $(i, j)$ entry is

$(\mathbf{AB})_{ij} = \sum_{k=1}^{n} A_{ik} B_{kj}$

Computing one entry of $\mathbf{AB}$ takes $n$ integer multiplications, and $\mathbf{AB}$ is an $m \times p$ matrix, so computing every entry takes $(m \times p) \times n = m \times n \times p$ integer multiplications in total.

The product is defined only when the number of columns of $\mathbf{A}$ equals the number of rows of $\mathbf{B}$. For example, a $3 \times 2$ matrix and a $4 \times 5$ matrix cannot be multiplied.

Matrix multiplication is not commutative, but it is associative. That is, for an $m \times n$ matrix $\mathbf{A}$, an $n \times p$ matrix $\mathbf{B}$, and a $p \times q$ matrix $\mathbf{C}$, the following holds in general.

• $\mathbf{AB} \neq \mathbf{BA}$
• $\mathbf{ABC} = (\mathbf{AB})\mathbf{C} = \mathbf{A}(\mathbf{BC})$

When several matrices are multiplied, the order in which they are listed cannot change, but the order in which the products are carried out is free. Does changing that order really change the number of integer multiplications? Let $\mathbf{A}$ be a $2 \times 4$ matrix, $\mathbf{B}$ a $4 \times 3$ matrix, and $\mathbf{C}$ a $3 \times 5$ matrix, and compute the product $\mathbf{ABC}$.

• Computing it as $(\mathbf{A}\mathbf{B})\mathbf{C}$
  • Multiplying the $2 \times 4$ matrix $\mathbf{A}$ by the $4 \times 3$ matrix $\mathbf{B}$ takes $2 \times 4 \times 3 = 24$ integer multiplications and produces a $2 \times 3$ matrix.
  • Multiplying the $2 \times 3$ matrix $\mathbf{A}\mathbf{B}$ by the $3 \times 5$ matrix $\mathbf{C}$ takes $2 \times 3 \times 5 = 30$ integer multiplications and produces a $2 \times 5$ matrix.
  • The total is $24 + 30 = 54$ integer multiplications.
• Computing it as $\mathbf{A}(\mathbf{B}\mathbf{C})$
  • Multiplying the $4 \times 3$ matrix $\mathbf{B}$ by the $3 \times 5$ matrix $\mathbf{C}$ takes $4 \times 3 \times 5 = 60$ integer multiplications and produces a $4 \times 5$ matrix.
  • Multiplying the $2 \times 4$ matrix $\mathbf{A}$ by the $4 \times 5$ matrix $\mathbf{B}\mathbf{C}$ takes $2 \times 4 \times 5 = 40$ integer multiplications and produces a $2 \times 5$ matrix.
  • The total is $60 + 40 = 100$ integer multiplications.

The count already depends on the order for three matrices, so it depends on the order for $n$ matrices as well. The more matrices there are, the more ways there are to multiply them. For example, when $n = 4$ there are five ways to multiply $\mathbf{M}_1, \mathbf{M}_2, \mathbf{M}_3, \mathbf{M}_4$.

• $\big((\mathbf{M}_1\mathbf{M}_2)\mathbf{M}_3\big)\mathbf{M}_4$
• $\big(\mathbf{M}_1(\mathbf{M}_2\mathbf{M}_3)\big)\mathbf{M}_4$
• $(\mathbf{M}_1\mathbf{M}_2)(\mathbf{M}_3\mathbf{M}_4)$
• $\mathbf{M}_1\big((\mathbf{M}_2\mathbf{M}_3)\mathbf{M}_4\big)$
• $\mathbf{M}_1\big(\mathbf{M}_2(\mathbf{M}_3\mathbf{M}_4)\big)$

Every way gives the same result, so picking the way that needs the fewest integer multiplications minimizes the time spent multiplying.

Seunghyun likes computing, and he recently learned how to multiply $n$ matrices like this. After working through a few examples he fell for multiplication. He says that multiplying entries and adding all of the products up is beautiful.

Seunghyun performs an integer multiplication in zero time, so he began to wonder whether the number of integer multiplications really has to be minimized, and he asked his teacher. The teacher answered that the gap between the worst count and the optimal count is sometimes quite large, so for an ordinary person, who spends real time on an integer multiplication, keeping the count small matters. Here the worst and the optimal count of integer multiplications are the counts of the way that needs the most and the way that needs the fewest integer multiplications, among all the ways of multiplying the matrices.

Seunghyun could not relate to ordinary people at all, so he kept asking. Worn out by the questions, the teacher finally answered that for every natural number $K$ there are matrices $\mathbf{M}_1, \mathbf{M}_2, \cdots, \mathbf{M}_n$ whose worst count and optimal count of integer multiplications differ by exactly $K$.

Shocked, Seunghyun asked you to find one such family of matrices. Given $K$, write a program that finds the sizes of matrices whose worst count and optimal count of integer multiplications differ by exactly $K$.

The first line contains an integer $K$ ($1 \le K \le 10^9$).

On the first line print the number of matrices $N$ ($1 \le N \le 100$). On the second line print $N+1$ positive integers $a_0, a_1, \ldots, a_N$, separated by spaces, giving the sizes of the matrices. The matrix sizes are $a_0 \times a_1$, $a_1 \times a_2$, ..., $a_{N-1} \times a_N$ in that order, and the worst count and the optimal count of integer multiplications for multiplying these $N$ matrices must differ by exactly $K$.

If several answers satisfy the condition, print only the lexicographically smallest one. That is, first take an answer with the smallest $N$, and among answers with the same $N$ take the one whose sequence $(a_0, a_1, \ldots, a_N)$ is smallest when compared from the front.