Задачи
Сумма простыми числами
Сумма простыми числами
Натуральное число может быть выражено в виде суммы различных простых чисел тем или иным способом. Для двух заданных натуральных чисел \textbf{n} и \textbf{k} Вам необходимо найти количество способов, которыми можно выразить \textbf{n} в виде суммы \textbf{k} различных простых чисел. Два способа считаются одинаковыми, если они дают в итоге один и тот же набор простых чисел. Например, \textbf{8} может быть выражено как \textbf{3 + 5} и \textbf{5 + 3}, но эти способы не различаются.
Например, при \textbf{n} = \textbf{24 }и \textbf{k} = \textbf{3 }ответом будет два, так как имеется всего два множества \{\textbf{2}, \textbf{3}, \textbf{19}\} и \{\textbf{2}, \textbf{5}, \textbf{17}\}, суммы которых равны \textbf{24}. Нет никаких других наборов из трех простых чисел, которые в сумме дают \textbf{24}. Для \textbf{n = 24} и \textbf{k = 2} ответ будет три, потому что есть три множества \{\textbf{5}, \textbf{19}\}, \{\textbf{7}, \textbf{17}\} и \{\textbf{11}, \textbf{13}\}. Для \textbf{n = 2} и \textbf{k = 1} ответ один, потому что есть только один набор \{\textbf{2}\}, сумма которого равна \textbf{2}. Для \textbf{n = 1} и \textbf{k = 1} ответ равен нулю. Число \textbf{1} не является простым, вы не должны учитывать \{\textbf{1}\}. Для \textbf{n = 4} и \textbf{k = 2} ответ равен нулю, потому что нет никаких наборов из двух различных простых чисел, сумма которых равна \textbf{4}.
Необходимо написать программу, которая вычислит количество таких способов для заданных \textbf{n }и \textbf{k}.
\InputFile
Каждая строка является отдельным тестом и содержит два натуральных числа \textbf{n (n} ≤ \textbf{1120)} и \textbf{k} (\textbf{k} ≤ \textbf{14}), разделенных пробелом. Последня строка содержит два ноля и не обрабатывается.
\OutputFile
Для каждого теста в отдельной строке вывести количество способов, которыми можно представить число \textbf{n }в виде суммы \textbf{k }различных простых слагаемых. Считайте, что все ответы будут меньше \textbf{2^31}.
Входные данные #1
24 3 24 2 2 1 1 1 4 2 18 3 17 1 17 3 17 4 100 5 1000 10 1120 14 0 0
Выходные данные #1
2 3 1 0 0 2 1 0 1 55 200102899 2079324314