#include <utility>
#include <vector>
std::vector< std::pair<int, int> > factor_table;
void fill_sieve( int n )
{
factor_table.resize(n+1);
for( int i = 1; i <= n; ++i )
factor_table[i] = std::pair<int, int>(i, 1);
for( int j = 2, j2 = 4; j2 <= n; (j2 += j), (j2 += ++j) ) {
if (factor_table[j].second == 1) {
int i = j;
int ij = j2;
while (ij <= n) {
factor_table[ij] = std::pair<int, int>(j, i);
++i;
ij += j;
}
}
}
}
std::vector<unsigned> powers;
template<int dir>
void factor( int num )
{
while (num != 1) {
powers[factor_table[num].first] += dir;
num = factor_table[num].second;
}
}
void calc_catalan(unsigned N)
{
powers.resize(2*N+1);
for( unsigned k = 2; k <= N; ++k ) {
factor<+1>(k+N);
factor<-1>(k);
}
}
#include <iostream>
#include <cmath>
int main(void)
{
fill_sieve(20000);
unsigned N = 9913;
unsigned long long M = 1000000000007LL;
calc_catalan(N);
char* sep = "";
unsigned long long result = 1;
for( unsigned i = 0; i < powers.size(); ++i ) {
while (powers[i]--) {
result *= i;
result %= M;
}
}
std::cout << "Catalan(" << N << ") modulo " << M << " = " << result << "\n\n";
}
I2luY2x1ZGUgPHV0aWxpdHk+CiNpbmNsdWRlIDx2ZWN0b3I+CgpzdGQ6OnZlY3Rvcjwgc3RkOjpwYWlyPGludCwgaW50PiA+IGZhY3Rvcl90YWJsZTsKdm9pZCBmaWxsX3NpZXZlKCBpbnQgbiApCnsKCWZhY3Rvcl90YWJsZS5yZXNpemUobisxKTsKCWZvciggaW50IGkgPSAxOyBpIDw9IG47ICsraSApCgkJZmFjdG9yX3RhYmxlW2ldID0gc3RkOjpwYWlyPGludCwgaW50PihpLCAxKTsKCWZvciggaW50IGogPSAyLCBqMiA9IDQ7IGoyIDw9IG47IChqMiArPSBqKSwgKGoyICs9ICsraikgKSB7CgkJaWYgKGZhY3Rvcl90YWJsZVtqXS5zZWNvbmQgPT0gMSkgewoJCQlpbnQgaSA9IGo7CgkJCWludCBpaiA9IGoyOwoJCQl3aGlsZSAoaWogPD0gbikgewoJCQkJZmFjdG9yX3RhYmxlW2lqXSA9IHN0ZDo6cGFpcjxpbnQsIGludD4oaiwgaSk7CgkJCQkrK2k7CgkJCQlpaiArPSBqOwoJCQl9CgkJfQoJfQp9CgpzdGQ6OnZlY3Rvcjx1bnNpZ25lZD4gcG93ZXJzOwoKdGVtcGxhdGU8aW50IGRpcj4Kdm9pZCBmYWN0b3IoIGludCBudW0gKQp7Cgl3aGlsZSAobnVtICE9IDEpIHsKCQlwb3dlcnNbZmFjdG9yX3RhYmxlW251bV0uZmlyc3RdICs9IGRpcjsKCQludW0gPSBmYWN0b3JfdGFibGVbbnVtXS5zZWNvbmQ7Cgl9Cn0KCnZvaWQgY2FsY19jYXRhbGFuKHVuc2lnbmVkIE4pCnsKICAgIHBvd2Vycy5yZXNpemUoMipOKzEpOwogICAgZm9yKCB1bnNpZ25lZCBrID0gMjsgayA8PSBOOyArK2sgKSB7CiAgICAgICAgIGZhY3RvcjwrMT4oaytOKTsKICAgICAgICAgZmFjdG9yPC0xPihrKTsKICAgIH0KfQoKI2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8Y21hdGg+CiAgICBpbnQgbWFpbih2b2lkKQogICAgewogICAgICAgIGZpbGxfc2lldmUoMjAwMDApOwogICAgICAgIHVuc2lnbmVkIE4gPSA5OTEzOwogICAgICAgIHVuc2lnbmVkIGxvbmcgbG9uZyBNID0gMTAwMDAwMDAwMDAwN0xMOwogICAgICAgIGNhbGNfY2F0YWxhbihOKTsKICAgICAgICBjaGFyKiBzZXAgPSAiIjsKICAgICAgICB1bnNpZ25lZCBsb25nIGxvbmcgcmVzdWx0ID0gMTsKICAgICAgICBmb3IoIHVuc2lnbmVkIGkgPSAwOyBpIDwgcG93ZXJzLnNpemUoKTsgKytpICkgewogICAgICAgICAgICB3aGlsZSAocG93ZXJzW2ldLS0pIHsKICAgICAgICAgICAgICAgIHJlc3VsdCAqPSBpOwogICAgICAgICAgICAgICAgcmVzdWx0ICU9IE07CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICAgICAgc3RkOjpjb3V0IDw8ICJDYXRhbGFuKCIgPDwgTiA8PCAiKSBtb2R1bG8gIiA8PCBNIDw8ICIgPSAiIDw8IHJlc3VsdCA8PCAiXG5cbiI7CiAgICB9