e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Competitions

Dynamic programming

Catalan numbers

Catalan numbers cn are given by recurrence relation:

prb9643.gif

Compute the n-th Catalan numbers modulo m.

Input

Two integers n (0n104) and m (0 < m109).

Output

Print the value of cn mod m.

Time limit 1 second
Memory limit 128 MiB
Input example #1
5 100
Output example #1
42
Author Michael Medvedev