\textit{Присвячується лектору другого дня Харківської Зимової Школи 2011 з програмування }\textit{\textbf{Дмитру Жукову}}\textit{.} \includegraphics{https://static.e-olymp.com/content/46/46a44d5e44e2eb8ca5d57c3d219c6a8aa2f0d52f.jpg} Коли Андрій уважно слухав лекцію Дмитра Жукова, у залі пролунала фраза “Метелики Фур'є”, від якої Андрій здригнувся і задумався: "\textit{…на вулиці кінець лютого і мінус }\textit{\textbf{25}}\textit{, коли ж нарешті настане весна і з'являться метелики?"} Від про майбутню весну, тепло і метелоків він перестав уважно слухати лектора і так і не зрозумів алгоритм Карацуби. По приїзді додому він запитав учителя: -- \textit{А що це за метелики Фур'є?} ­-- \textit{Послухай, я тобі краще розповім про інших метеликів, про яких мені розповідав мій викладач, коли я був трішки старшим за тебе і навчався у ВУЗі. Можливо вони зможуть тобі якось допомогти, коли тт будеш самостійно розбиратись удома з лекцією Дмитра Жукова…} Алгоритм розрахований на швидке множення подумки \textbf{2}-х \textbf{n}-значних чисел. Запишемо на дошці два \textbf{n}-значних числа (зрозуміло, що якщо одне з чисел коротше -- ми зможемо спереду дописати потрібну нам кількість не значущих нулів). Згадаємо фразу: "\textit{З молодших класів ми знаємо табличку множення}". Що означає ця фраза з точки зору програміста? А означає вона те, що ми можемо створити двомірний масив, куди занести табличку множення для цифр від \textbf{0} до \textbf{9} і при виконанні подальших обчислень не множити заново дві цифри, а взяти готове число з пам'яті -- адже ми вже знаємо табличку множення!!! Тоді правила для швидкого множення \textbf{n}-значних чисел можна записати наступним чином: ­Для однозначних чисел правило називається \textbf{I} -- ми множимо дві цифри одна над другою. \includegraphics{https://static.e-olymp.com/content/59/59478eb6d63e259fa72725ae39549502447ebe12.jpg} Для двозначних чисел правило називається \textbf{IXI}. Відмітимо, що усі правила виконуються зправа наліво. Покажемо, як це правило діє у порівнянні зі звичайним множенням у стовбчик. Тому для початку наведемо приклад звичайного множення для чисел \textbf{25} і \textbf{37}: Тепер пояснимо, як ми можем обійтись без проміжних рядків, які нам потім потрібно додавати. Помножимо (візьмемо з таблички множення!!!) дві праві цифри \textbf{5} і \textbf{7} -- виконаємо праве \textbf{I}. Останню цифру результату \textbf{5} запишемо відразу у відповіль, а інші цифри (у даному випадку лише одну цифру \textbf{3}) перенесемо у наступний розряд. Тепер виконаємо \textbf{X}. Для цього кладемо подумки \textbf{2∙7} та \textbf{3∙5} і додамо перенос \textbf{3}. Отримаємо \textbf{14 + 15 + 3 = 32}. Знову запишемо в результат отриману останню цифру \textbf{2} і запам'ятаємо перенос \textbf{3}. Виконаємо ліве \textbf{I}: \textbf{2∙3 = 6}, додамо до нього перенос \textbf{3} і запишемо в результат \textbf{9}. У підсумку наша послвдовність виконання дій на дошці буде мати вигляд, як це показано на рисунку нижче і ліворуч. \includegraphics{https://static.e-olymp.com/content/fb/fbd73e0cb02c34f039a73c555adaf0fc21fbd3a9.jpg} Для тризначних чисел діє правило \textbf{IXЖXI} і так далі -- на кожному етапі максимальний метелик має на одну пару "крильців" більше, ніж попередня. -- \textit{Ну як, Андрій, ти зрозумів як тепер можна швидко множити довгі числа?} -- \textit{О, звичано -- зараз реалізую і випробую на задачці }"\href{/problems/272}{Добуток}". Алгоритм Андрій реалізуваі, і задачку здав, а ось тепер задачка для Вас: яке число було перенесено у алгоритмі Андрія на \textbf{k}-тому кроці? \InputFile У перших двох рядках задано почтакові числа \textbf{A} та \textbf{B} (\textbf{A}, \textbf{B} ≤ \textbf{10^10000}), кожне у своєму рядку. У третьому рядку задано число \textbf{k} (\textbf{1} ≤ \textbf{k} ≤ \textbf{20001}). \OutputFile Єдине число, запомнене для переносу, при виконанні множення в один рядок.