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 mention of "Fourier Butterflies" resonated through the hall. This made Andriy shiver and think: "...it's the end of February and minus 25 degrees, when will spring finally come and butterflies appear?" As he daydreamed about spring, warmth, and butterflies, he lost track of the lecture and missed the explanation of the Karatsuba algorithm.
When he got home, he asked his teacher:
– What are these Fourier Butterflies?
– Let me tell you about a different kind of butterfly, which my teacher shared with me when I was just a bit older than you and studying at university. Perhaps this will help you understand Dmytro Zhukov's lecture when you revisit it at home...
This algorithm is designed for the fast mental multiplication of 2 n-digit numbers. Imagine writing two n-digit numbers on the board (if one number is shorter, you can add leading zeros to make them equal in length). Remember 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 to store the multiplication table for digits from 0 to 9. This way, during calculations, we don't need to multiply two digits again; we can simply retrieve the result from memory since we already know the multiplication table!
The rules for fast multiplication of n-digit numbers are as follows:
For single-digit numbers, the rule is called I – you multiply two digits directly above each other.
For two-digit numbers, the rule is called IXI. Note that all rules are applied from right to left. Let's demonstrate how this rule works compared to regular column multiplication. First, here's an example of regular multiplication for the numbers 25 and 37:
Now, let's see how we can avoid intermediate rows, which we would otherwise need to add. Multiply (retrieve from the multiplication table!) the two rightmost digits 5 and 7 – this is the right I. Write the last digit of the result 5 immediately in the answer, and carry over the other digits (in this case, just one digit 3) to the next position. Now perform X. For this, mentally compute 2∙7 and 3∙5 and add the carry 3. This gives 14 + 15 + 3 = 32. Again, write the last digit 2 in the result and remember the carry 3. Perform the left I: 2∙3 = 6, add the carry 3 to it, and write 9 in the result. In the end, our sequence of actions on the board will look as shown in the picture 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 one.
– Well, Andriy, do you understand how you can now quickly multiply long numbers?
– Oh, of course – I'll implement it now and test it on the task "Product".
Andriy implemented the algorithm and solved the task, and now here's a challenge for you: what number was carried over in Andriy's algorithm on the k-th step?
Input
The first two lines contain the initial numbers A and B (A, B ≤ 10^10000), each on its own line. The third line contains the number k (1 ≤ k ≤ 20001).
Output
Output the single number that was carried over during multiplication at the k-th step.