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