22139번 - Трисолианцы 다국어

Недавно стало известно, что жители планеты Трисол обозначают свой возраст не одним целым числом, как мы — земляне, а вектором из k целых чисел. Считается, что у новорождённого трисолианца вектор его возраста состоит из k нулей. По мере взросления, каждый год, к каждому элементу вектора возраста прибавляется некоторое положительное число.

Историей жизни трисолианца называется набор всех векторов его возраста, которые были у него в течение жизни. Земные учёные установили, что не существует двух трисолианцев с одинаковой историей.

Теперь ученых интересует — у какого максимального числа трисолианцев, история жизни заканчивается на векторе, сумма элементов которого равна n. Напишите программу, которая вычисляет это значение по модулю простого числа 7340033 = 7·2²⁰ + 1.

Например, если k = 2, то может существовать 8 трисолианцев, у которых история жизни заканчивается на векторе с суммой 5. Их истории жизни следующие:

• (0, 0) - (1, 1) - (2, 3);
• (0, 0) - (1, 1) - (3, 2);
• (0, 0) - (1, 2) - (2, 3);
• (0, 0) - (1, 4);
• (0, 0) - (2, 1) - (3, 2);
• (0, 0) - (2, 3);
• (0, 0) - (3, 2);
• (0, 0) - (4, 1).

Первая строка содержит два целых числа n и k — сумма элементов последнего вектора возраста, и количество элементов в векторе (1 ≤ n ≤ 4239, 1 ≤ k ≤ 10⁹).

Выведите максимальное число трисолианцев, история жизни которых может заканчивается на векторе, сумма элементов которого равна n. Ответ следует вывести по модулю 7340033 = 7·2²⁰ + 1.