Note that the memory limit in this problem is lower than in others.

You have a vertical strip with n cells, numbered consecutively from 1 to n from top to bottom.

You also have a token that is initially placed in cell n. You will move the token up until it arrives at cell 1.

Let the token be in cell x > 1 at some moment. One shift of the token can have either of the following kinds: 

  * Subtraction: you choose an integer y between 1 and x-1, inclusive, and move the token from cell x to cell x - y. 
  * Floored division: you choose an integer z between 2 and x, inclusive, and move the token from cell x to cell ⌊ x/z ⌋ (x divided by z rounded down). 



Find the number of ways to move the token from cell n to cell 1 using one or more shifts, and print it modulo m. Note that if there are several ways to move the token from one cell to another in one shift, all these ways are considered distinct (check example explanation for a better understanding).

Input

The only line contains two integers n and m (2 ≤ n ≤ 4 ⋅ 10^6; 10^8 < m < 10^9; m is a prime number) — the length of the strip and the modulo.

Output

Print the number of ways to move the token from cell n to cell 1, modulo m.

Examples

Input


3 998244353


Output


5


Input


5 998244353


Output


25


Input


42 998244353


Output


793019428


Input


787788 100000007


Output


94810539

Note

In the first test, there are three ways to move the token from cell 3 to cell 1 in one shift: using subtraction of y = 2, or using division by z = 2 or z = 3.

There are also two ways to move the token from cell 3 to cell 1 via cell 2: first subtract y = 1, and then either subtract y = 1 again or divide by z = 2.

Therefore, there are five ways in total.

Difficulty: HARD
Tags: Dynamic programming

Number theory

Mathematics

Complete search
Skill types: Dynamic programming

Complete search

Starter code:

Solutions:
(n, m) = map(int, input().split())
c = [0] * n + [1] + [0] * n
for i in range(n - 1, 0, -1):
	c[i] = 2 * c[i + 1] % m
	for j in range(2, n // i + 1):
		c[i] = (c[i] + c[i * j] - c[(i + 1) * j]) % m
print((c[1] - c[2]) % m)


import sys
from array import array
input = sys.stdin.readline

def ri():
	return [int(i) for i in input().split()]

def rs():
	return input().split()[0]

def main():
	t = 1
	for _ in range(t):
		(n, m) = ri()
		sum = [0] * (n + 2)
		sum[n] = 1
		sum[n + 1] = 0
		last = -1
		for x in range(n - 1, 0, -1):
			extra = sum[x + 1]
			for d in range(2, n // x + 1):
				from_ = x * d
				to_ = min(x * d + d - 1, n)
				extra = (extra + sum[from_] - sum[to_ + 1]) % m
			last = extra
			sum[x] = (sum[x + 1] + last) % m
		print(last % m)
main()


def naiveSolve():
	return

def solve():
	return

def main():
	(n, MOD) = readIntArr()

	def addAcrossRange(l, r, val):
		diffArr[l] += val
		diffArr[l] %= MOD
		diffArr[r + 1] -= val
		diffArr[r + 1] = (diffArr[r + 1] + MOD) % MOD

	def getVal(i):
		return diffArr[i] - diffArr[i - 1]
	diffArr = [0] * (n + 5)
	arr = [0] * (n + 5)
	diffArr[1] = 1
	diffArr[2] = -1
	arr[1] = 1
	currVal = 0
	prefixSum = 0
	for i in range(1, n + 1):
		currVal += diffArr[i]
		currVal %= MOD
		arr[i] = currVal
		prefixSum += arr[i]
		prefixSum %= MOD
		addAcrossRange(i + 1, i + 1, prefixSum)
		z = 1
		while True:
			left = i * z
			if z == 1:
				left += 1
			right = i * z + z - 1
			right = min(right, n)
			if left > n:
				break
			addAcrossRange(left, right, arr[i])
			z += 1
	ans = arr[n]
	print(ans)
	return
import sys
input = lambda : sys.stdin.readline().rstrip('\r\n')

def oneLineArrayPrint(arr):
	print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
	print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
	print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
	return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
	dv = defaultValFactory
	da = dimensionArr
	if len(da) == 1:
		return [dv() for _ in range(da[0])]
	else:
		return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(x):
	print('{}'.format(x))
	sys.stdout.flush()
	return int(input())

def answerInteractive(ans):
	print('! {}'.format(ans))
	sys.stdout.flush()
inf = float('inf')
MOD = 998244353
from math import gcd, floor, ceil
for _abc in range(1):
	main()


(n, mod) = map(int, input().split())
dp = [0] * (n + 1)
dp[-1] = 1
for i in range(n - 1, 0, -1):
	dp[i] = (dp[i + 1] + dp[i + 1]) % mod
	for j in range(2, n // i + 1):
		dp[i] = (dp[i] + dp[i * j] - (dp[i * j + j] if i * j + j <= n else 0)) % mod
print((dp[1] - dp[2]) % mod)


(N, MOD) = map(int, input().split())
DP = [0] * N
DP[0] = 1
Cum = [0] * (N + 1)
Cum[1] = 1
for i1 in range(1, N):
	i2 = N - i1
	Value = Cum[i1]
	for j in range(2, N + 1):
		if i2 * j > N:
			break
		Value += Cum[N - i2 * j + 1] - Cum[max(0, N - i2 * j - j + 1)]
		Value %= MOD
	Cum[i1 + 1] += Cum[i1] + Value
	Cum[i1 + 1] %= MOD
	DP[i1] = Value
print(DP[-1])


from io import BytesIO, IOBase
import sys
import math
import os
import heapq
from collections import defaultdict, deque
from math import ceil
from bisect import bisect_left, bisect_left
from time import perf_counter
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def input():
	return sys.stdin.readline().rstrip('\r\n')

def mint():
	return map(int, input().split())

def mfloat():
	return map(float, input().split())

def intin():
	return int(input())

def solve():
	(n, mod) = map(int, input().split())
	dp = [0] * (n + 1)
	dp[-1] = 1
	current = 1
	suffix_sum = [0] * (n + 1)
	suffix_sum[-1] = 1
	for i in range(n - 1, 0, -1):
		dp[i] = suffix_sum[i + 1]
		for j in range(2, n + 1):
			if i * j > n:
				break
			dp[i] += suffix_sum[i * j] - (suffix_sum[i * j + j] if i * j + j <= n else 0)
			dp[i] %= mod
		suffix_sum[i] = (suffix_sum[i + 1] + dp[i]) % mod
	print(dp[1] % mod)

def main():
	t = 1
	for _ in range(t):
		solve()
start_time = perf_counter()
main()
print(perf_counter() - start_time, file=sys.stderr)


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
DP = [0] * (n + 5)
CUM = [1] * (n + 5)
CUM[1] = 0
DP[1] = 1
S = 1
for i in range(2, n + 1):
	CUM[i] = (CUM[i - 1] + CUM[i]) % m
	DP[i] = (S + CUM[i]) % m
	S += DP[i]
	S %= m
	for j in range(i + i, n + 1, i):
		CUM[j] = (CUM[j] + DP[i] - DP[i - 1]) % m
print(DP[n])


from __future__ import division, print_function
import math
import sys
import os
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input().strip()
	return list(s[:len(s)])

def invr():
	return map(int, input().split())

def Divisors(n):
	i = 1
	fac = []
	while i <= int(math.sqrt(n)):
		if n % i == 0:
			if n // i == i:
				fac.append(i)
			else:
				fac.append(i)
				fac.append(n // i)
		i = i + 1
	return fac
(n, maxn) = invr()
dp = [1 for i in range(n + 1)]
dp[0] = 0
dp[2] = 0
for i in range(2, n + 1):
	dp[i] += 2 * dp[i - 1] % maxn
	for j in range(2 * i, n + 1, i):
		dp[j] += (dp[i] - dp[i - 1]) % maxn
		dp[j] = dp[j] % maxn
	dp[i] = dp[i] % maxn
print(dp[n])


from sys import stdin
input = stdin.readline

def add(x, y):
	return (x % mod + y % mod) % mod

def sub(x, y):
	return (x - y + mod) % mod

def answer():
	dp = [0] * (n + 1)
	prefix = [0] * (n + 2)
	dp[n] = 1
	for i in range(n, 0, -1):
		dp[i] = add(dp[i], prefix[i + 1])
		j = 2
		while i * j <= n:
			dp[i] = add(dp[i], prefix[i * j])
			if j * i + j <= n:
				dp[i] = sub(dp[i], prefix[j * i + j])
			j += 1
		prefix[i] = add(prefix[i + 1], dp[i])
	return dp[1]
for T in range(1):
	(n, mod) = map(int, input().split())
	print(answer())


import os
import sys
from io import BytesIO, IOBase

def main():
	(n, m) = map(int, input().split())
	dp = [0] * (n + 1)
	pre = [0] * (n + 2)
	su = 0
	for i in range(1, n + 1):
		pre[i] = (pre[i] + pre[i - 1]) % m
		dp[i] = (su + pre[i] + (i == 1)) % m
		su = (su + dp[i]) % m
		for j in range(2, n // i + 1):
			pre[i * j] = (pre[i * j] + dp[i]) % m
			z = min(i * j + j, n + 1)
			pre[z] = (pre[z] - dp[i]) % m
	print(dp[-1])
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


(n, m) = map(int, input().split())
dp = [0 for i in range(n + 3)]
dp2 = [0 for i in range(n + 3)]
dp[n] = 1
dp2[n] = 1
for i in range(n - 1, 0, -1):
	dp[i] = dp2[i + 1] % m
	mul = 2
	while i * mul <= n:
		dp[i] = (dp[i] % m + dp2[i * mul] % m - dp2[min((i + 1) * mul, n + 1)] % m) % m
		mul += 1
	dp2[i] = (dp[i] % m + dp2[i + 1] % m) % m
print(dp[1] % m)


import os
import sys
import math
import collections
import functools
import itertools
import heapq
import bisect
from io import BytesIO, IOBase

def vsInput():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
ALPHA = 'abcde'
MOD = 10 ** 9 + 7
EPS = 1e-06

def Ceil(a, b):
	return a // b + int(a % b > 0)

def INT():
	return int(input())

def STR():
	return input()

def INTS():
	return tuple(map(int, input().split()))

def ARRINT():
	return [int(i) for i in input().split()]

def ARRSTR():
	return [i for i in input().split()]
(n, MOD) = INTS()
dp = [0] * (n + 2)
dp[n] = 1
for i in range(n - 1, 0, -1):
	tmp = dp[i + 1]
	j = 2
	while i * j < n + 2:
		tmp += dp[i * j] - dp[min(n + 1, (i + 1) * j)]
		tmp %= MOD
		j += 1
	dp[i] = tmp + dp[i + 1]
	dp[i] %= MOD
print((dp[1] - dp[2]) % MOD)


import sys
from io import BytesIO, IOBase
import os
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self, **kwargs):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def inp():
	return sys.stdin.readline().strip()

def map_inp(v_type):
	return map(v_type, inp().split())

def list_inp(v_type):
	return list(map_inp(v_type))
(n, m) = map_inp(int)
dp = [0 for col in range(n + 1)]
add_q = [0 for item in range(n + 2)]
dp[n] = 1
add_q[n] = 1
for i in range(n - 1, 0, -1):
	dp[i] += add_q[i + 1] % m
	z = 2
	for temp in range(i * z, n + 1, i):
		left = i * z
		right = min(i * z + z - 1, n)
		dp[i] += add_q[left] - add_q[right + 1]
		dp[i] %= m
		z += 1
	add_q[i] += dp[i] + add_q[i + 1]
	add_q[i] %= m
print(dp[1])


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
mod = m
dp = [0] * (n + 3)
dp[n] = 1
sdp = [0] * (n + 3)
sdp[n] = 1
for x in range(n - 1, 0, -1):
	dp[x] += sdp[x + 1]
	dp[x] %= mod
	z = 2
	while x * z <= n:
		l = x * z
		r = (x + 1) * z - 1
		if r > n:
			r = n
		dp[x] += sdp[l] - sdp[r + 1]
		dp[x] %= mod
		z += 1
	sdp[x] = sdp[x + 1] + dp[x]
	sdp[x] %= mod
print(dp[1] % mod)


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
dp = [0] * (n + 1)
dp[1] = 1
dp[2] = 2
for i in range(2, n + 1):
	if i > 2:
		dp[i] = ((dp[i] + dp[i - 1]) % m + dp[i - 1] + 1) % m
	for j in range(i + i, n + 1, i):
		dp[j] = (dp[j] + dp[i] - dp[i - 1]) % m
print(dp[n])


(n, m) = map(int, input().split())
sumL = [0] * (n + 2)
L = 1
sumL[-2] = 1
for i in range(n - 1, 0, -1):
	L = sumL[i + 1]
	j = 2
	while i * j <= n:
		L += sumL[i * j] - sumL[min(n, (i + 1) * j - 1) + 1]
		L %= m
		j += 1
	L %= m
	sumL[i] = sumL[i + 1] + L
	sumL[i] %= m
print(L)


from sys import stdin, stdout
from bisect import bisect_left, bisect_right
from math import ceil, floor, log, gcd, sqrt
from collections import Counter, deque
from heapq import heappush, heappop, heapify

def re():
	return stdin.readline().rstrip()

def ints():
	return map(int, stdin.readline().split())

def test(tc):
	for _ in range(tc):
		solve()
mod = 1000000007
nl = '\n'

class Dsu:

	def __init__(self, n):
		self.parent = list(range(n))
		self.rank = [1] * n

	def find(self, x):
		while x != self.parent[x]:
			self.parent[x] = self.parent[self.parent[x]]
			x = self.parent[x]
		return x

	def union(self, x, y):
		(px, py) = (self.find(x), self.find(y))
		if px == py:
			return 0
		if self.rank[py] > self.rank[px]:
			(px, py) = (py, px)
		self.parent[py] = px
		self.rank[px] += self.rank[py]
		return 1

	def get_size(self, x):
		return self.rank[self.find(x)]

class SegTree:

	def __init__(self, n, array):
		self.n = n
		self.tree = [0] * (2 * n)
		for i in range(n, 2 * n):
			self.tree[i] = array[i - n]
		for i in range(n - 1, -1, -1):
			self.tree[i] = self.tree[2 * i] + self.tree[2 * i + 1]

	def update(self, i, val):
		self.tree[i] = val
		while i:
			self.tree[i] = self.tree[i * 2] + self.tree[i * 2 + 1]
			i //= 2

	def query(self):
		pass

	def top(self):
		return self.tree[0]

def solve():
	(n, m) = ints()
	dp = [0] * (n + 1)
	dp[n] = 1
	suf = [0] * (n + 2)
	suf[n] = 1
	for i in range(n - 1, 0, -1):
		dp[i] = suf[i + 1] % m
		for mul in range(2, n + 1):
			lo = i * mul
			hi = (i + 1) * mul - 1
			if lo > n:
				break
			dp[i] = (dp[i] + suf[lo] - suf[min(n, hi) + 1]) % m
		suf[i] = (suf[i + 1] + dp[i]) % m
	print(dp[1] % m)
	return
test(1)


from __future__ import division, print_function
import os, sys
from io import BytesIO, IOBase
if sys.version_info[0] < 3:
	from __builtin__ import xrange as range
	from future_builtins import ascii, filter, hex, map, oct, zip
from bisect import bisect_left as lower_bound, bisect_right as upper_bound

def so():
	return int(input())

def st():
	return input()

def mj():
	return map(int, input().strip().split(' '))

def msj():
	return map(str, input().strip().split(' '))

def le():
	return list(map(int, input().split()))

def lebe():
	return list(map(int, input()))

def dmain():
	sys.setrecursionlimit(1000000)
	threading.stack_size(1024000)
	thread = threading.Thread(target=main)
	thread.start()

def joro(L):
	return ''.join(map(str, L))

def decimalToBinary(n):
	return bin(n).replace('0b', '')

def isprime(n):
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return False
	return True

def npr(n, r):
	return factorial(n) // factorial(n - r) if n >= r else 0

def ncr(n, r):
	return factorial(n) // (factorial(r) * factorial(n - r)) if n >= r else 0

def lower_bound(li, num):
	answer = -1
	start = 0
	end = len(li) - 1
	while start <= end:
		middle = (end + start) // 2
		if li[middle] >= num:
			answer = middle
			end = middle - 1
		else:
			start = middle + 1
	return answer

def upper_bound(li, num):
	answer = -1
	start = 0
	end = len(li) - 1
	while start <= end:
		middle = (end + start) // 2
		if li[middle] <= num:
			answer = middle
			start = middle + 1
		else:
			end = middle - 1
	return answer

def abs(x):
	return x if x >= 0 else -x

def binary_search(li, val, lb, ub):
	ans = -1
	while lb <= ub:
		mid = (lb + ub) // 2
		if li[mid] > val:
			ub = mid - 1
		elif val > li[mid]:
			lb = mid + 1
		else:
			ans = mid
			break
	return ans

def kadane(x):
	sum_so_far = 0
	current_sum = 0
	for i in x:
		current_sum += i
		if current_sum < 0:
			current_sum = 0
		else:
			sum_so_far = max(sum_so_far, current_sum)
	return sum_so_far

def pref(li):
	pref_sum = [0]
	for i in li:
		pref_sum.append(pref_sum[-1] + i)
	return pref_sum

def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	li = []
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	for p in range(2, len(prime)):
		if prime[p]:
			li.append(p)
	return li

def primefactors(n):
	factors = []
	while n % 2 == 0:
		factors.append(2)
		n //= 2
	for i in range(3, int(sqrt(n)) + 1, 2):
		while n % i == 0:
			factors.append(i)
			n //= i
	if n > 2:
		factors.append(n)
	return factors

def read():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

def tr(n):
	return n * (n + 1) // 2

def fb(k, L):
	if k == L[k]:
		return k
	if L[k] == fb(L[k], L):
		return L[k]

def usa(a, b, Y, Z):
	a = fb(a, Y)
	b = fb(b, Y)
	if a != b:
		if Z[a] < Z[b]:
			(a, b) = (b, a)
		Y[b] = a
		Z[a] += Z[b]

def iu():
	import sys
	input = sys.stdin.buffer.readline
	import math as my
	(p, q) = mj()
	if p == 1:
		print(1)
		return
	L = []
	P = []
	for i in range(p + 1):
		L.append(1)
		P.append(0)
	P[1] = 1
	P[2] = 2
	j = 4
	while j < 1 + p:
		L[j] = L[2] + L[j]
		j = 2 + j
	i = 3
	while i < 1 + p:
		L[i] = P[i - 1] + L[i]
		L[i] %= q
		j = i * 2
		while j < 1 + p:
			L[j] = L[i] + L[j]
			L[j] %= q
			j += i
		P[i] = (P[i - 1] + L[i]) % q
		i += 1
	print(P[p])

def main():
	for i in range(1):
		iu()
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()