Path Counting on Factor Graph

Given a number line with points from \(1\) to \(n\). Each point \(i\) can jump to one of the following positions:

• \(i+1\) if \(i+1 \le n\)
• \(i-1\) if \(i-1 \ge 1\)
• Any proper divisor \(d\) of \(i\) (i.e. any \(d\) with \(d|i\) and \(d < i\))

Each point can be visited at most once. Two jump moves are considered different if either the destination differs at some step or the jump type (i.e. normal backward/forward or divisor jump) differs. Calculate the number of distinct sequences of jumps from point \(n\) to point \(1\) and output the answer modulo \(p\).

inputFormat

The input consists of two integers \(n\) and \(p\). Here, \(n\) is the number of points on the number line, and \(p\) is the modulus.

outputFormat

Output a single integer, which is the number of distinct jump sequences from point \(n\) to point \(1\) modulo \(p\).

sample

3 100

3