#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <numeric>
#include <iomanip>

#define REP(i,n) for(i=0; i < (n); i++)
#define REPONE(i, n) for(i=1; i <= (n); i++)
#define LOOP(n) for(int loopCount=1; loopCount <= (n); loopCount++)
#define ITER(c) __typeof((c).begin())
#define EACH(c,it) for(ITER(c) it =(c).begin(); it!=(c).end(); it++)
#define SZ(c) ((int) (c).size())
#define ALL(c) c.begin(), c.end()
#define SUM(c) accumulate(ALL(c), 0)
#define EXIST(c,v) (find(ALL(c), (v)) != (c).end())
#define PB push_back
#define MP make_pair

using namespace std;
static const double EPS = 1e-9;
static const double PI = 3.141592653589793238462643383279;
typedef long long ll;

vector<int> ps;

void primeTable(int n){
    vector<int> table(n+1, 0);
    for(int i=2; i<=n; i++){
        if(!table[i]){
            ps.push_back(i);
        if(i <= sqrt(n)) table[i*i] = i;
        }
        else{
        int j = i, step = table[i];
            while(j+step<=n){
                if(!table[j+step]) {
                    table[j+step] = step;
                    break;
                }
                else {
                    int tmp = step;
                    step = table[j+step];
                    table[j+tmp] = tmp;
                    j += tmp;
                }
            }
        }
    }
}

#define N 1120

int main(){
    ps.PB(-1);
    primeTable(N);
    static int dp[N+2][190][16];
    int i, j, k, l, n, ans, s = SZ(ps);
    REP(i,N+2)REP(j,190)REP(k,16) dp[i][j][k] = 0;
    dp[0][0][0] = 1;
    REP(i,N){
        REP(j,s+1)REP(k,15)if(dp[i][j][k]){
            for(l=j+1; l<s && i + ps[l] <= N; l++){
                dp[i+ps[l]][l][k+1] += dp[i][j][k];
            }
        }
    }

    while(scanf("%d%d",&n,&k)){
        if(!(n||k)) break;
        ans = 0;
        REP(j,190) ans += dp[n][j][k];
        printf("%d\n",ans);
    }

    return 0;
}
### Prompt

Please create a solution in cpp 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 <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <numeric>
#include <iomanip>

#define REP(i,n) for(i=0; i < (n); i++)
#define REPONE(i, n) for(i=1; i <= (n); i++)
#define LOOP(n) for(int loopCount=1; loopCount <= (n); loopCount++)
#define ITER(c) __typeof((c).begin())
#define EACH(c,it) for(ITER(c) it =(c).begin(); it!=(c).end(); it++)
#define SZ(c) ((int) (c).size())
#define ALL(c) c.begin(), c.end()
#define SUM(c) accumulate(ALL(c), 0)
#define EXIST(c,v) (find(ALL(c), (v)) != (c).end())
#define PB push_back
#define MP make_pair

using namespace std;
static const double EPS = 1e-9;
static const double PI = 3.141592653589793238462643383279;
typedef long long ll;

vector<int> ps;

void primeTable(int n){
    vector<int> table(n+1, 0);
    for(int i=2; i<=n; i++){
        if(!table[i]){
            ps.push_back(i);
        if(i <= sqrt(n)) table[i*i] = i;
        }
        else{
        int j = i, step = table[i];
            while(j+step<=n){
                if(!table[j+step]) {
                    table[j+step] = step;
                    break;
                }
                else {
                    int tmp = step;
                    step = table[j+step];
                    table[j+tmp] = tmp;
                    j += tmp;
                }
            }
        }
    }
}

#define N 1120

int main(){
    ps.PB(-1);
    primeTable(N);
    static int dp[N+2][190][16];
    int i, j, k, l, n, ans, s = SZ(ps);
    REP(i,N+2)REP(j,190)REP(k,16) dp[i][j][k] = 0;
    dp[0][0][0] = 1;
    REP(i,N){
        REP(j,s+1)REP(k,15)if(dp[i][j][k]){
            for(l=j+1; l<s && i + ps[l] <= N; l++){
                dp[i+ps[l]][l][k+1] += dp[i][j][k];
            }
        }
    }

    while(scanf("%d%d",&n,&k)){
        if(!(n||k)) break;
        ans = 0;
        REP(j,190) ans += dp[n][j][k];
        printf("%d\n",ans);
    }

    return 0;
}
```