title: What is the fastest (known) algorithm to find the n-th Catalan number mod m?
body: <p>The problem is to find the <strong>n-th Catalan</strong> number mod <code>m</code>, where <code>m</code> is <strong>NOT prime</strong>, <code>m = (10^14 + 7)</code>. Here are the list of methods that I have tried: (max <code>N = 10,000</code>)</p>
  
  <ol>
  <li>Dynamic programming for table look-up, too slow </li>
  <li>Use Catalan formula <code>ncr(2*n, n)/(n + 1)</code>, again it wasn't fast enough due to the <code>ncr</code> function, can't speed up using <strong>exponentiation squaring</strong> because <code>m</code> is not prime.</li>
  <li>Hardcode a table of pre-generated <code>Catalans</code>, but it failed due to the file size limit.</li>
  <li>Recurrence relation <code>C(i,k) = C(i-1,k-1) + C(i-1,k)</code>, this is way too slow</li>
  </ol>
  
  <p>So I wonder is there any other faster algorithm to find the <strong>n-th Catalan</strong> number that I'm not aware of?</p>
  
  <p><strong>Using Dynamic Programming</strong> </p>
  
  <pre><code>void generate_catalan_numbers() {
      catalan[1] = 1;
      for (int i = 2; i &lt;= MAX_NUMBERS; i++) {
          for (int j = 1; j &lt;= i - 1; j++) {
              catalan[i] = (catalan[i] + ((catalan[j]) * catalan[i - j]) % MODULO) % MODULO;
          }
          catalan[i] = catalan[i] % MODULO;
      }
  }
  </code></pre>
  
  <p><strong>Using original formula</strong></p>
  
  <pre><code>ull n_choose_r(ull n, ull r) {
      if (n &lt; r)
          return 0;
  
      if (r &gt; n/2) {
          r = n - r;
      }
  
      ull result = 1;
      ull common_divisor;
      for (int i = 1; i &lt;= r; ++i) {
          common_divisor = gcd(result, i);
          result /= common_divisor;
          result *= (n - i + 1) / (i / common_divisor);
      }
  
      return result;
  }
  </code></pre>
  
  <p><strong>Using recurrence relation</strong></p>
  
  <pre><code>ull n_choose_r_relation(ull n, ull r) {
      for (int i = 0; i &lt;= n + 1; ++i) {
          for (int k = 0; k &lt;= r &amp;&amp; k &lt;= i; ++k) {
              if (k == 0 || k == i) {
                  ncr[i][k] = 1;
              }
              else {
                  ncr[i][k] = (ncr[i - 1][k - 1] + ncr[i - 1][k]) % MODULO;
              }
          }
      }
  
      return ncr[n][r];
  }
  </code></pre>