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.
//Utilities
import java.io.*;
import java.util.*;

public class D {
	static int n;
	static int M;
	static long[] dp, sum;
	
	public static void main(String[] args) throws IOException {
		n = in.iscan(); M = in.iscan(); dp = new long[n+1]; sum = new long[n+1];
		dp[n] = 1; sum[n] = 1;
		int y = 1;
		for (int i = n-1; i >= 1; i--) {
			dp[i] = sum[i+1];
			while (i * (y+1) <= n) {
				y++;
			}
			int l, r;
			for (int x = 2; x <= y; x++) {
				l = i * x;
				r = Math.min(n, i * x + x - 1);
				dp[i] = (dp[i] + sumRange(l, r)) % M;
			}
			sum[i] = (sum[i+1] + dp[i]) % M;
		}
		out.println(dp[1]);
		out.close();
	}
	
	static long sumRange(int l, int r) {
		if (r != n) {
			return ((sum[l] - sum[r+1]) % M + M) % M;
		}
		return sum[l];
	}
	
	static INPUT in = new INPUT(System.in);
	static PrintWriter out = new PrintWriter(System.out);
	private static class INPUT {

		private InputStream stream;
		private byte[] buf = new byte[1024];
		private int curChar, numChars;

		public INPUT (InputStream stream) {
			this.stream = stream;
		}

		public INPUT (String file) throws IOException {
			this.stream = new FileInputStream (file);
		}

		public int cscan () throws IOException {
			if (curChar >= numChars) {
				curChar = 0;
				numChars = stream.read (buf);
			}
			
			if (numChars == -1)
				return numChars;

			return buf[curChar++];
		}

		public int iscan () throws IOException {
			int c = cscan (), sgn = 1;
			
			while (space (c))
				c = cscan ();

			if (c == '-') {
				sgn = -1;
				c = cscan ();
			}

			int res = 0;

			do {
				res = (res << 1) + (res << 3);
				res += c - '0';
				c = cscan ();
			}
			while (!space (c));

			return res * sgn;
		}

		public String sscan () throws IOException {
			int c = cscan ();
			
			while (space (c))
				c = cscan ();

			StringBuilder res = new StringBuilder ();

			do {
				res.appendCodePoint (c);
				c = cscan ();
			}
			while (!space (c));

			return res.toString ();
		}

		public double dscan () throws IOException {
			int c = cscan (), sgn = 1;
			
			while (space (c))
				c = cscan ();

			if (c == '-') {
				sgn = -1;
				c = cscan ();
			}

			double res = 0;

			while (!space (c) && c != '.') {
				if (c == 'e' || c == 'E')
					return res * UTILITIES.fast_pow (10, iscan ());
				
				res *= 10;
				res += c - '0';
				c = cscan ();
			}

			if (c == '.') {
				c = cscan ();
				double m = 1;

				while (!space (c)) {
					if (c == 'e' || c == 'E')
						return res * UTILITIES.fast_pow (10, iscan ());

					m /= 10;
					res += (c - '0') * m;
					c = cscan ();
				}
			}

			return res * sgn;
		}

		public long lscan () throws IOException {
			int c = cscan (), sgn = 1;
			
			while (space (c))
				c = cscan ();

			if (c == '-') {
				sgn = -1;
				c = cscan ();
			}

			long res = 0;

			do {
				res = (res << 1) + (res << 3);
				res += c - '0';
				c = cscan ();
			}
			while (!space (c));

			return res * sgn;
		}

		public boolean space (int c) {
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}
	}

	public static class UTILITIES {

		static final double EPS = 10e-6;
		
		public static void sort(int[] a, boolean increasing) {
			ArrayList<Integer> arr = new ArrayList<Integer>();
			int n = a.length;
			for (int i = 0; i < n; i++) {
				arr.add(a[i]);
			}
			Collections.sort(arr);
			for (int i = 0; i < n; i++) {
				if (increasing) {
					a[i] = arr.get(i);
				}
				else {
					a[i] = arr.get(n-1-i);
				}
			}
		}
		
		public static void sort(long[] a, boolean increasing) {
			ArrayList<Long> arr = new ArrayList<Long>();
			int n = a.length;
			for (int i = 0; i < n; i++) {
				arr.add(a[i]);
			}
			Collections.sort(arr);
			for (int i = 0; i < n; i++) {
				if (increasing) {
					a[i] = arr.get(i);
				}
				else {
					a[i] = arr.get(n-1-i);
				}
			}
		}
		
		public static void sort(double[] a, boolean increasing) {
			ArrayList<Double> arr = new ArrayList<Double>();
			int n = a.length;
			for (int i = 0; i < n; i++) {
				arr.add(a[i]);
			}
			Collections.sort(arr);
			for (int i = 0; i < n; i++) {
				if (increasing) {
					a[i] = arr.get(i);
				}
				else {
					a[i] = arr.get(n-1-i);
				}
			}
		}

		public static int lower_bound (int[] arr, int x) {
			int low = 0, high = arr.length, mid = -1;

			while (low < high) {
				mid = (low + high) / 2;

				if (arr[mid] >= x)
					high = mid;
				else
					low = mid + 1;
			}

			return low;
		}

		public static int upper_bound (int[] arr, int x) {
			int low = 0, high = arr.length, mid = -1;

			while (low < high) {
				mid = (low + high) / 2;

				if (arr[mid] > x)
					high = mid;
				else
					low = mid + 1;
			}

			return low;
		}
		
		public static void updateMap(HashMap<Integer, Integer> map, int key, int v) {
			if (!map.containsKey(key)) {
				map.put(key, v);
			}
			else {
				map.put(key, map.get(key) + v);
			}
			if (map.get(key) == 0) {
				map.remove(key);
			}
		}

		public static long gcd (long a, long b) {
			return b == 0 ? a : gcd (b, a % b);
		}

		public static long lcm (long a, long b) {
			return a * b / gcd (a, b);
		}

		public static long fast_pow_mod (long b, long x, int mod) {
			if (x == 0) return 1;
			if (x == 1) return b;
			if (x % 2 == 0) return fast_pow_mod (b * b % mod, x / 2, mod) % mod;

			return b * fast_pow_mod (b * b % mod, x / 2, mod) % mod;
		}

		public static int fast_pow (int b, int x) {
			if (x == 0) return 1;
			if (x == 1) return b;
			if (x % 2 == 0) return fast_pow (b * b, x / 2);

			return b * fast_pow (b * b, x / 2);
		}

		public static long choose (long n, long k) {
			k = Math.min (k, n - k);
			long val = 1;

			for (int i = 0; i < k; ++i)
				val = val * (n - i) / (i + 1);

			return val;
		}

		public static long permute (int n, int k) {
			if (n < k) return 0;
			long val = 1;

			for (int i = 0; i < k; ++i)
				val = (val * (n - i));

			return val;
		}
		
		// start of permutation and lower/upper bound template
		public static void nextPermutation(int[] nums) {
		    //find first decreasing digit
		    int mark = -1;
		    for (int i = nums.length - 1; i > 0; i--) {
		        if (nums[i] > nums[i - 1]) {
		            mark = i - 1;
		            break;
		        }
		    }
		 
		    if (mark == -1) {
		        reverse(nums, 0, nums.length - 1);
		        return;
		    }
		 
		    int idx = nums.length-1;
		    for (int i = nums.length-1; i >= mark+1; i--) {
		        if (nums[i] > nums[mark]) {
		            idx = i;
		            break;
		        }
		    }
		 
		    swap(nums, mark, idx);
		 
		    reverse(nums, mark + 1, nums.length - 1);
		}
		 
		public static void swap(int[] nums, int i, int j) {
		    int t = nums[i];
		    nums[i] = nums[j];
		    nums[j] = t;
		}
		 
		public static void reverse(int[] nums, int i, int j) {
		    while (i < j) {
		        swap(nums, i, j);
		        i++;
		        j--;
		    }
		}
		
		static int lower_bound (int[] arr, int hi, int cmp) {
			int low = 0, high = hi, mid = -1;
			while (low < high) {
				mid = (low + high) / 2;
				if (arr[mid] >= cmp) high = mid;
				else low = mid + 1;
			}
			return low;
		}
	 
		static int upper_bound (int[] arr, int hi, int cmp) {
			int low = 0, high = hi, mid = -1;
			while (low < high) {
				mid = (low + high) / 2;
				if (arr[mid] > cmp) high = mid;
				else low = mid + 1;
			}
			return low;
		}
		// end of permutation and lower/upper bound template
	}
}
