Пусть задана некоторая целочисленная последовательность \{\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}.