#include <iostream>
using namespace std;
int dp[105][105]; // R <= N <= 100
int ncr(int N, int R) {
if( R == 0 ) return 1;
else if( R > N/2 ) return ncr(N, N-R);
else if( dp[N][R] ) return dp[N][R];
return dp[N][R] = ncr(N-1,R-1) + ncr(N-1,R);
}
int main() {
cout << ncr(45, 6) << endl; // Lotto
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKaW50IGRwWzEwNV1bMTA1XTsgLy8gUiA8PSBOIDw9IDEwMAoKaW50IG5jcihpbnQgTiwgaW50IFIpIHsKCWlmKCBSID09IDAgKSByZXR1cm4gMTsKCWVsc2UgaWYoIFIgPiBOLzIgKSByZXR1cm4gbmNyKE4sIE4tUik7CgllbHNlIGlmKCBkcFtOXVtSXSApIHJldHVybiBkcFtOXVtSXTsKCQoJcmV0dXJuIGRwW05dW1JdID0gbmNyKE4tMSxSLTEpICsgbmNyKE4tMSxSKTsKfQoKaW50IG1haW4oKSB7Cgljb3V0IDw8IG5jcig0NSwgNikgPDwgZW5kbDsgLy8gTG90dG8KCXJldHVybiAwOwp9