Нехай задано деяку цілочисельну послідовність \{\textbf{a_n}\} довжини \textbf{n}, яка складається з невід'ємних чисел. Сформуємо з неї послідовність \{\textbf{b_n}\} довжини \textbf{n--1} за наступним правилом: \textbf{b_i = a_i + a_i_\{+1\}}. Провівші таке перетворення \textbf{n--1} раз, ми отримаємо послідовність довжини \textbf{1}, тобто одне число, яке позначимо через \textbf{k}. Вам потрібно розв'язати наступну задачу -- знаючи число \textbf{k}, визначте, скільки цілочисельних послідовностей довжини \textbf{n} з невід'ємними членами дають число \textbf{k} у результаті вищшеописаної процедури. \InputFile Два цілих числа \textbf{k} (\textbf{0} ≤ \textbf{k} ≤ \textbf{50000}) і \textbf{n} (\textbf{2} ≤ \textbf{n} ≤ \textbf{50000}). \OutputFile Одне ціле число, взяте по модулю \textbf{10^6}, -- кількість цілочисельних послідовностей довжини \textbf{n} з невід'ємними членами, які у результаті вищеописаної процедури дають число \textbf{k}.