#include<iostream>
#include<vector>
#include<cmath>
#include<algorithm>

using namespace std;

#define MAX 1200
#define P 188
#define N 1121
#define K 14

vector<int> vprimes;
bool *isPrime = new bool[MAX];

/* ツ素ツ青板青カツ青ャ O(n^2) */
void MakePrime(){
  isPrime[0]=false;
  isPrime[1]=false;
  isPrime[2]=true;
  for(int i = 2; i < MAX; ++i){
    isPrime[i] = true;
  }
  for(long long int i = 2; i < MAX; ++i){
    if( isPrime[i] ){
      for(long long int j = 2; i * j < MAX; ++j) {
	isPrime[i*j] = false;
      }
    }
  }
  for(int i = 0; i < MAX; ++i){
    if( isPrime[i] ){
      vprimes.push_back( i );
    }
  }
}

int table[P][N][K];
int next_big_prime_index[N];

int solve(int last_prime, int n, int k){
  int &t = table[last_prime][n][k];
  int ret = 0;
  if( k == 1 ){
    if( isPrime[ n ] && n > vprimes[last_prime] ){
      t = 1;
      return 1;
    }else{
      t = 0;
      return 0;
    }
  }else{
    if( t != -1 )return t;
    else{
      for(int i = last_prime+1; vprimes[i] < MAX && n - vprimes[i] > 0; ++i){
	ret += solve( i, n - vprimes[i], k-1);
      }
      table[last_prime][n][k] = ret;
      return ret;
    }
  }
}

int main(){
  MakePrime();
  //cout << vprimes.size()  << endl;
  vprimes.insert( vprimes.begin(), 0 );
  while(true){
    int n,k;
    cin >> n >> k;
    fill(&table[0][0][0],&table[P-1][N-1][K-1],-1);
    if( n == 0 && k == 0 ) break;
    cout << solve( 0, n, k ) << endl;
  }
  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<iostream>
#include<vector>
#include<cmath>
#include<algorithm>

using namespace std;

#define MAX 1200
#define P 188
#define N 1121
#define K 14

vector<int> vprimes;
bool *isPrime = new bool[MAX];

/* ツ素ツ青板青カツ青ャ O(n^2) */
void MakePrime(){
  isPrime[0]=false;
  isPrime[1]=false;
  isPrime[2]=true;
  for(int i = 2; i < MAX; ++i){
    isPrime[i] = true;
  }
  for(long long int i = 2; i < MAX; ++i){
    if( isPrime[i] ){
      for(long long int j = 2; i * j < MAX; ++j) {
	isPrime[i*j] = false;
      }
    }
  }
  for(int i = 0; i < MAX; ++i){
    if( isPrime[i] ){
      vprimes.push_back( i );
    }
  }
}

int table[P][N][K];
int next_big_prime_index[N];

int solve(int last_prime, int n, int k){
  int &t = table[last_prime][n][k];
  int ret = 0;
  if( k == 1 ){
    if( isPrime[ n ] && n > vprimes[last_prime] ){
      t = 1;
      return 1;
    }else{
      t = 0;
      return 0;
    }
  }else{
    if( t != -1 )return t;
    else{
      for(int i = last_prime+1; vprimes[i] < MAX && n - vprimes[i] > 0; ++i){
	ret += solve( i, n - vprimes[i], k-1);
      }
      table[last_prime][n][k] = ret;
      return ret;
    }
  }
}

int main(){
  MakePrime();
  //cout << vprimes.size()  << endl;
  vprimes.insert( vprimes.begin(), 0 );
  while(true){
    int n,k;
    cin >> n >> k;
    fill(&table[0][0][0],&table[P-1][N-1][K-1],-1);
    if( n == 0 && k == 0 ) break;
    cout << solve( 0, n, k ) << endl;
  }
  return 0;
}
```