Execution time limit is 1 second Runtime memory usage limit is 128 megabytes Catalan numbers cn are given by recurrence relation:
c0=1,cn=k=0∑n−1ckcn−k−1,n>0
Compute the n-th Catalan numbers modulo m.
Input
Two integers n (0≤n≤104) and m (0<m≤109).
Output
Print the value of cn mod m.
Examples