Дано три цілих числа \textbf{N}, \textbf{a} і \textbf{b}. Потрібно знайти залишок від ділення на число \textbf{1000000007} (\textbf{10^9+7}) кількості натуральних чисел \textbf{X}, для яких одночасно справджуються такі три умови: \begin{enumerate} \item \textbf{X} ≤ \textbf{N}; \item \textbf{X} кратне \textbf{2^a}; \item сума цифр числа \textbf{X} кратна \textbf{2^b}. \end{enumerate} \InputFile Перший рядок вхідного файлу містить \textbf{2} цілих числа: \textbf{a} та \textbf{b} (\textbf{0} ≤ \textbf{a} ≤ \textbf{9}, \textbf{0} ≤ \textbf{b} ≤ \textbf{9}). Другий рядок містить число \textbf{N} (\textbf{1} ≤ \textbf{N} ≤ \textbf{10^5000}). \OutputFile Вихідний файл має містити одне число --- залишок від ділення на число \textbf{1000000007} (\textbf{10^9+7}) кількості натуральних чисел \textbf{X}, для яких справджуються усі умови \textbf{1--3}, подані вище.