#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>

using namespace std;


#define NUM 1120

int main(){
	int table[NUM],limit;

	for(int i=0; i < NUM;i++)table[i] = 1;
	table[0] = 0;
	table[1] = 0;

	limit = sqrt(NUM);

	for(int i=2;i<=limit;i++){
		if(table[i] == 1){
			for(int k=2*i;k < NUM; k += i){
				table[k] = 0;
			}
		}
	}

	int prime_table[NUM],index = 0;

	for(int i = 2; i < NUM; i++){
		if(table[i] == 1){
			prime_table[index++] = i;
		}
	}

	int*** dp = new int**[15];
	for(int i = 0; i < 15; i++){
		dp[i] = new int*[index];
		for(int k = 0; k < index; k++){
			dp[i][k] = new int[1121];
		}
	}

	for(int i = 0; i < 15; i++){
		for(int k = 0; k < index; k++){
			for(int p = 0; p < 1121; p++)dp[i][k][p] = 0;
		}
	}

	for(int i = 0; i < index; i++){
		dp[1][i][prime_table[i]] = 1;
	}

	for(int k = 2; k <= 14; k++){
		for(int i = 1; i < index; i++){
			for(int p = 0; p <= i-1; p++){
				for(int a = prime_table[i]+1; a <= 1120; a++){
					dp[k][i][a] += dp[k-1][p][a-prime_table[i]];
				}
			}
		}
	}

	int A,B,sum;

	while(true){
		scanf("%d %d",&A,&B);
		if(A == 0 && B == 0)break;

		sum = 0;

		for(int i = 0; i < index; i++)sum += dp[B][i][A];

		printf("%d\n",sum);

	}

	return 0;
}
### Prompt

Construct a Cpp code solution to the problem outlined:

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 <stdio.h>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>

using namespace std;


#define NUM 1120

int main(){
	int table[NUM],limit;

	for(int i=0; i < NUM;i++)table[i] = 1;
	table[0] = 0;
	table[1] = 0;

	limit = sqrt(NUM);

	for(int i=2;i<=limit;i++){
		if(table[i] == 1){
			for(int k=2*i;k < NUM; k += i){
				table[k] = 0;
			}
		}
	}

	int prime_table[NUM],index = 0;

	for(int i = 2; i < NUM; i++){
		if(table[i] == 1){
			prime_table[index++] = i;
		}
	}

	int*** dp = new int**[15];
	for(int i = 0; i < 15; i++){
		dp[i] = new int*[index];
		for(int k = 0; k < index; k++){
			dp[i][k] = new int[1121];
		}
	}

	for(int i = 0; i < 15; i++){
		for(int k = 0; k < index; k++){
			for(int p = 0; p < 1121; p++)dp[i][k][p] = 0;
		}
	}

	for(int i = 0; i < index; i++){
		dp[1][i][prime_table[i]] = 1;
	}

	for(int k = 2; k <= 14; k++){
		for(int i = 1; i < index; i++){
			for(int p = 0; p <= i-1; p++){
				for(int a = prime_table[i]+1; a <= 1120; a++){
					dp[k][i][a] += dp[k-1][p][a-prime_table[i]];
				}
			}
		}
	}

	int A,B,sum;

	while(true){
		scanf("%d %d",&A,&B);
		if(A == 0 && B == 0)break;

		sum = 0;

		for(int i = 0; i < index; i++)sum += dp[B][i][A];

		printf("%d\n",sum);

	}

	return 0;
}
```