//중복조합이라 오버플로우에 시간까지 오래걸리는 코드
#include <iostream>
#include <algorithm>
long long dp[201] ;
using namespace std;
long long fact(long long num) {
	if (dp[num] != 0)
		return dp[num];
	else
		return num * fact(num - 1);
}
int main() {
	int n,k;
	long long r = 1000000000;
	scanf_s("%d %d",&n,&k);

	//(n+k-1)!/(n)!(k-1)!
	long long answer = fact(n + k - 1) / fact(n) * fact(k-1);
	answer = answer % r;
	
	cout << answer;	
}

// 점화식으로 짠 코드
// for문에서 변수의 범위와 초기값을 반드시 확인할 것
// 나머지 계산을 할때는 순서를 잘 고려해야 한다!
#include <iostream>
#include <algorithm>
using namespace std;
long long dp[2][201]; 
long long r = 1000000000;
int main() {
	int n, k;
	scanf_s("%d %d", &n, &k);
	int b = 0;

	for (int i = 0; i <= n; i++)
		dp[b][i] = 1;

	//dp[k][n] = dp[k-1][n-1] + dp[k-1][n-2] + ... + dp[k-1][0]
	for (int i = 2; i <= k; i++) {
		b = !b;
		for (int nn = 0; nn <= n; nn++) {
			dp[b][nn] = 0;
			for (int pp = 0; pp <= nn; pp++) {
				dp[b][nn] += dp[!b][pp];
			}
			dp[b][nn] %= r;
		}
	}
	cout<< dp[b][n];
}

//https://www.acmicpc.net/source/7599835
//점화식을 순서대로 계산해보면 나타나는 규칙이 있다.
// 1 1 1 1 1 1...
// 1 2 3 4 5 6...
// 1 3 6 10 15 21...
// 1 4 10 20 35 56...
//이렇게 누적되서 계산하는 방식으로 코드를 짜면 2중for문으로 줄일 수 있다.
#include<stdio.h>
int arr[210],n,k,sum,i,j;
int main(void){
    scanf("%d %d",&n,&k);
    for(i=0;i<=n;i++)arr[i]=1;
    for(j=1;j<k;j++)
        for(i=1;i<=n;i++)
            arr[i]+=arr[i-1],arr[i]%=1000000000;
    printf("%d",arr[n]);
    return 0;
}

#include <iostream>
#include <string>
using namespace std;
long long mod = 1000000;
long long dp[2];//0:맨 뒤 알파벳이 1자리수 (A,B,C..)인 경우의 수, 
				//1:맨 뒤 알파벳이 2자리수(Z,Y,X..)인 경우의 수
bool isAlphabet(int ten, int one) {
	int val= (ten - 48) * 10 + one - 48;
	if (val >= 10 && val <= 26)
		return true;
	return false;
}
bool isAlphabet(int one) {
	if (one - 48 == 0)
		return false; //0
	return true; // 1~9
}
int main(void) {
	string str;
	cin >> str;
	int length = str.length();

	if (!isAlphabet(str[0])){
		cout << 0; return 0;
	}
	dp[0] = 1, dp[1] = 0;

	for (int i = 1; i < str.length(); i++) {
		if (dp[0] == 0 && dp[1] == 0) {
			cout << 0;	return 0;
		}
		else {
			long long dp0 = dp[0];
			long long dp1 = dp[1];
			dp[0] = isAlphabet(str[i]) ? (dp0 + dp1)%mod : 0;
			dp[1] = isAlphabet(str[i - 1], str[i]) ? dp0 : 0;
		}
	}
	printf("%lld", (dp[0]+dp[1])%mod);
}

//https://www.acmicpc.net/source/2145920
/*
입력에서 예외가 발생했다.
scanf_s 문자열 배열의 크기를 인식하지 못해서 생기는 문제라는데
==> scanf_s("%s", name, sizeof(name));
아래 코드는 c++11이라서 가능했던 것 같다.
*/
#include <cstdio>
#define MOD	1000000
int main() {
	int d[5001] = { 1, 0, }, cnt = 0;
	char a[5001];
	scanf("%s", a); //입력

	for (int i = 0; a[i]; i++)	cnt++; //문자열길이 구하기
	if (a[0] - '0' > 0)	d[1] = 1; //처음 수가 1~9 인지.

	for (int i = 2; i <= cnt; i++) {
		if (a[i - 1] - '0' > 0)		
			d[i] += d[i - 1];
		if (a[i - 2] - '0' > 0 && (a[i - 2] - '0') * 10 + (a[i - 1] - '0') <= 26)	
			d[i] += d[i - 2];
		d[i] %= MOD;
	}
	printf("%d\n", d[cnt]);
}

#include <iostream>
#include <algorithm>
using namespace std;
int p[1001]; //카드팩 별 가격 pi
int f[1001]; //x개를 구매할때 최대 가격
int main() {
	int n;
	scanf_s("%d", &n);
	for (int i = 1; i <= n; i++)
		scanf_s("%d", &p[i]);

	f[0] = 0;
	for (int i = 1; i <= n; i++) {
		f[i] = p[i];
		for (int j = 1; j <= i; j++) {
			f[i] = max(f[i], p[j] + f[i - j]);
		}
	}
	cout << f[n];
}

//https://www.acmicpc.net/source/4562643
#include <stdio.h>
int main(){
	int a=0, b=0, i=0, j=0, A[2000]={0, };
	scanf("%d", &a);
	for(i=0;i<a;i++) 
    	scanf("%d", A+i);
	for(i=0;i<a;i++){
    	for(j=0;j<i;j++){
        	if(A[i]<A[j]+A[i-1-j]) 
                A[i]=A[j]+A[i-j-1];
    	}
	}
	printf("%d", A[i-1]);
}