CSES - HIIT Open 2017 - 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

• 1 \le n,m \le 10^9

# 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)].