David Copperfield is resting

Dedicated to the lecturer of the second day of the Kharkiv Winter School 2011 on programming, Dmytro Zhukov.

While Andriy was attentively listening to Dmytro Zhukov's lecture, the phrase "Fourier Butterflies" resonated through the hall. It made Andriy shiver and think: "...it's the end of February and minus $25$ degrees, when will spring finally come and butterflies appear?" Lost in thoughts about spring, warmth, and butterflies, he stopped paying attention to the lecturer and ended up missing the explanation of the Karatsuba algorithm.

At home, he asked his teacher:

– What are these Fourier Butterflies?

– Let me tell you about a different kind of butterfly, which my teacher told me about when I was a bit older than you and in university. Perhaps they will help you understand Dmytro Zhukov's lecture when you look at it at home...

This algorithm is designed for fast mental multiplication of $2$ $n$-digit numbers. Write two $n$-digit numbers on the board (if one number is shorter, you can add leading zeros to make them equal in length). Recall the phrase: "From the lower grades, we know the multiplication table". From a programmer's perspective, this means we can create a two-dimensional array for the multiplication table of digits from $0$ to $9$, and for further calculations, we just retrieve the precomputed value instead of multiplying two digits each time—since we already know the table!

The rules for fast multiplication of $n$-digit numbers are as follows:

For single-digit numbers, the rule is I: multiply the two digits directly above each other.

For two-digit numbers, the rule is IXI. Note that all rules are performed from right to left. Let's show how this rule works compared to regular column multiplication. So, for starters, here's the ordinary multiplication for $25$ and $37$:

Now, let's explain how we can skip the intermediate rows that usually need to be added. Multiply (retrieve from the table!) the rightmost digits $5$ and $7$—this is the right I. Write the last digit $5$ directly in the answer, and carry over the rest of the digits (here, just $3$) to the next position. Now perform X: mentally sum 2 \cdot 7 and 3 \cdot 5 and add the carry-over $3$, for a total of 14 + 15 + 3 = 32. Again, write the last digit $2$ in the result and remember the carry $3$. Now perform the left I: 2 \cdot 3 = 6, add the carry $3$, and write $9$ in the result. In the end, the sequence of actions on the board is as shown below and to the left.

For three-digit numbers, the rule is IXЖXI, and so on—at each stage, the largest butterfly has one more pair of "wings" than the previous.

– So, Andriy, do you now understand how to quickly multiply long numbers?

– Oh, of course—I'll implement it and test it on the task "Product".

Andriy implemented the algorithm and solved the problem, but now the question for you: what number was carried over on the $k$-th step in Andriy's algorithm?