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