Code Submission Evaluation System Login

CSES - HIIT Open 2017

HIIT Open 2017

Contest start:2017-05-27 11:00:00
Contest end:2017-05-27 16:00:00

Task list | Submit code | Submissions | Messages | Scoreboard


Book writing

Time limit:0.50 s
Memory limit:512 MB

Kaaleppi will write a book of $n$ pages. There will be some chapters and sections, so that each chapter contains one or more sections, and each section consists of one or more pages.

For example, if $n=9$, one possible structure is $[(2)(4)][(3)]$. In this case there are two chapters. The first chapter contains two sections with $2$ and $4$ pages, and the second chapter contains one section with $3$ pages.

Your task is to calculate the total number of possible structures for the book. Since the answer may be large, output it modulo $m$.

Input

The only input line contains two integers $n$ and $m$: the number of pages and the modulo.

Output

Print the total number of structures modulo $m$.

Constraints
Example

Input:
3 123

Output:
9

Explanation: There are 9 possible structures: $[(3)]$, $[(1)(2)]$, $[(2)(1)]$, $[(1)(1)(1)]$, $[(1)][(2)]$, $[(2)][(1)]$, $[(1)][(1)(1)]$, $[(1)(1)][(1)]$ and $[(1)][(1)][(1)]$.