#include <iostream>
#include <algorithm>
#include <cstdio>
#include <string>
#include <cstring>
#include <cctype>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <map>
#include <numeric>
using namespace std;
 
#define REP(i, s, e) for (int i = (s); i < (e); i++)
#define REPI(i, s, e) for (int i = (s); i <= (e); i++)
#define rep(i, n) REP(i, 0, n)
#define repi(i, n) REPI(i, 0, n)
#define ALL(v) (v).begin(), (v).end()
 
#define dump(x) (cout << #x << " = " << x << endl)
#define dump2(x, y) (cout << "(" << #x << ", " << #y << ") = (" << x << ", " << y << ")" << endl)
#define dump3(x, y, z) (cout << "(" << #x << ", " << #y << ", " << #z << ") = (" << x << ", " << y << ", "<< z << ")" << endl)
 
typedef long long ll;
typedef pair<int, int> pii;

int n, k;

const int MAX = 1121;
int pp[MAX];
vector<int> primes;

void erat()
{
	memset(pp, -1, sizeof(pp));

	pp[0] = pp[1] = 0;
	for (int i = 2; i < MAX; i++)
		for (int j = 2*i; j < MAX; j += i)
			pp[j] = 0;

	rep(i, MAX)
		if (pp[i])
			primes.push_back(i);
}

const int K_MAX = 16;
const int P_MAX = 190;

ll dp[MAX][K_MAX][P_MAX];

ll solve(int s, int c, int i)
{
	if (s == n && c == k) return dp[s][c][i] = 1;
	if (s >= n || c == k) return 0;
	if (dp[s][c][i] != -1) return dp[s][c][i];
	if (!(i < primes.size())) return dp[s][c][i] = 0;

	int cnt = 0;
	cnt += solve(s+primes[i], c+1, i+1);
	cnt += solve(s, c, i+1);
	return dp[s][c][i] = cnt;
}

int main()
{
	erat();
	const int psz = primes.size();
	while (cin >> n >> k, n|k) {
		memset(dp, -1, sizeof(dp));
		cout << solve(0, 0, 0) << endl;

		/*
		memset(dp, 0, sizeof(dp));
		for (int s = n; s >= 0; s--) {
			for (int c = k; c >= 0; c--) {
				for (int i = psz-1; i >= 0; i--) {
					if (s == n && c == k) {
						dp[s][c][i] = 1;
					} else {
						dp[s][c][i] = 0;
						if (s+primes[i] <= n)
							dp[s][c][i] += dp[s+primes[i]][c+1][i+1];
						dp[s][c][i] += dp[s][c][i+1];
					}
				}
			}
		}
		cout << dp[0][0][0] << endl;
		*/
	}
	return 0;
}
### Prompt

Your challenge is to write a CPP solution to the following problem:

A positive integer may be expressed as a sum of different prime numbers (primes), in one way or another. Given two positive integers n and k, you should count the number of ways to express n as a sum of k different primes. Here, two ways are considered to be the same if they sum up the same set of the primes. For example, 8 can be expressed as 3 + 5 and 5+ 3 but they are not distinguished.

When n and k are 24 and 3 respectively, the answer is two because there are two sets {2, 3, 19} and {2, 5, 17} whose sums are equal to 24. There are no other sets of three primes that sum up to 24. For n = 24 and k = 2, the answer is three, because there are three sets {5, 19}, {7,17} and {11, 13}. For n = 2 and k = 1, the answer is one, because there is only one set {2} whose sum is 2. For n = 1 and k = 1, the answer is zero. As 1 is not a prime, you shouldn't count {1}. For n = 4 and k = 2, the answer is zero, because there are no sets of two diffrent primes whose sums are 4.

Your job is to write a program that reports the number of such ways for the given n and k.



Input

The input is a sequence of datasets followed by a line containing two zeros separated by a space. A dataset is a line containing two positive integers n and k separated by a space. You may assume that n ≤ 1120 and k ≤ 14.

Output

The output should be composed of lines, each corresponding to an input dataset. An output line should contain one non-negative integer indicating the number of ways for n and k specified in the corresponding dataset. You may assume that it is less than 231.

Example

Input

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


Output

2
3
1
0
0
2
1
0
1
55
200102899
2079324314

### Response

```cpp
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <string>
#include <cstring>
#include <cctype>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <map>
#include <numeric>
using namespace std;
 
#define REP(i, s, e) for (int i = (s); i < (e); i++)
#define REPI(i, s, e) for (int i = (s); i <= (e); i++)
#define rep(i, n) REP(i, 0, n)
#define repi(i, n) REPI(i, 0, n)
#define ALL(v) (v).begin(), (v).end()
 
#define dump(x) (cout << #x << " = " << x << endl)
#define dump2(x, y) (cout << "(" << #x << ", " << #y << ") = (" << x << ", " << y << ")" << endl)
#define dump3(x, y, z) (cout << "(" << #x << ", " << #y << ", " << #z << ") = (" << x << ", " << y << ", "<< z << ")" << endl)
 
typedef long long ll;
typedef pair<int, int> pii;

int n, k;

const int MAX = 1121;
int pp[MAX];
vector<int> primes;

void erat()
{
	memset(pp, -1, sizeof(pp));

	pp[0] = pp[1] = 0;
	for (int i = 2; i < MAX; i++)
		for (int j = 2*i; j < MAX; j += i)
			pp[j] = 0;

	rep(i, MAX)
		if (pp[i])
			primes.push_back(i);
}

const int K_MAX = 16;
const int P_MAX = 190;

ll dp[MAX][K_MAX][P_MAX];

ll solve(int s, int c, int i)
{
	if (s == n && c == k) return dp[s][c][i] = 1;
	if (s >= n || c == k) return 0;
	if (dp[s][c][i] != -1) return dp[s][c][i];
	if (!(i < primes.size())) return dp[s][c][i] = 0;

	int cnt = 0;
	cnt += solve(s+primes[i], c+1, i+1);
	cnt += solve(s, c, i+1);
	return dp[s][c][i] = cnt;
}

int main()
{
	erat();
	const int psz = primes.size();
	while (cin >> n >> k, n|k) {
		memset(dp, -1, sizeof(dp));
		cout << solve(0, 0, 0) << endl;

		/*
		memset(dp, 0, sizeof(dp));
		for (int s = n; s >= 0; s--) {
			for (int c = k; c >= 0; c--) {
				for (int i = psz-1; i >= 0; i--) {
					if (s == n && c == k) {
						dp[s][c][i] = 1;
					} else {
						dp[s][c][i] = 0;
						if (s+primes[i] <= n)
							dp[s][c][i] += dp[s+primes[i]][c+1][i+1];
						dp[s][c][i] += dp[s][c][i+1];
					}
				}
			}
		}
		cout << dp[0][0][0] << endl;
		*/
	}
	return 0;
}
```