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.


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


Print the total number of structures modulo m.


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



3 123



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