Catalan numbers

Easy

Execution time limit is 1 second

Runtime memory usage limit is 128 megabytes

Catalan numbers $c_{n}$ are given by recurrence relation:

c_{0} = 1, c_{n} = k = 0 \sum n - 1 c_{k} c_{n - k - 1}, n > 0

Compute the $n$ -th Catalan numbers modulo $m$ .

Input

Two integers $n (0 \leq n \leq 1 0^{4})$ and $m (0 < m \leq 1 0^{9})$ .

Print the value of $c_{n} m o d m$ .

Input #1

Answer #1

Submissions 1K

Acceptance rate 16%