Catalan numbers cn are given by recurrence relation:

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.