This version of the problem differs from the next one only in the constraint on n.

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 ≤ 2 ⋅ 10^5; 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

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.
import java.util.*;
import java.io.*;
public class Test {
	public static void main(String[] args) throws IOException {
	   Scanner sc = new Scanner(System.in);
	   PrintWriter pw = new PrintWriter(System.out);
	   int  n = sc.nextInt(); mod = sc.nextInt();
	   int [] dp = new int[n+1];
	   int [] pre = new int[n+1];
	   pre[1] = 1;
	   pre[2] = 3;
	   dp[1] = 1;
	   dp[2] = 2;
	  
	   for(int i = 3;i<=n;i++) {
		   dp[i] = pre[i-1] %mod;
		   dp[i] = (dp[i]+(i-(i/2))%mod)%mod;
		   //System.out.println(dp[i]);
		   int last = i/2;;
		   for(int j = 2;j*j<=i;j++) {
		   int div = i/j;
		   dp[i] = (dp[i]+dp[div])%mod;
		   if (div > j) {
		   int freq = (dp[j]%mod*(div-i/(j+1)%mod))% mod;
		   dp[i] = (dp[i]+freq)%mod;
		   last = i/(j+1);}
		   
	   }
		   
		   pre[i] = (pre[i-1]%mod+dp[i]%mod)%mod;
	   
	  }
	     System.out.println(dp[n]+" ");   
	
	}
	static int mod;
	public static double solve(int currTrial, int lampsMask) {
		if(lampsMask ==0 || currTrial==101) {
			return (currTrial-1);
		}
		if(dp[currTrial][lampsMask]!=-1) {
			return dp[currTrial][lampsMask];
		}
		double tot = 0;
		for(int i = 0;i<m;i++) {
			tot += (solve(currTrial+1,lampsMask^switchMask[i])/m);
		}
	    
		return dp[currTrial][lampsMask] = (tot);
		
	}
	static double [][] dp ;
	static double probFactor;
	static int m;
	static int [] switchMask;
    static int lcs(char[] X, char[] Y, int m, int n)
     {
         if (m == 0 || n == 0)
             return 0;
         if (X[m - 1] == Y[n - 1])
             return 1 + lcs(X, Y, m - 1, n - 1);
         else
             return Math.max(lcs(X, Y, m, n - 1), lcs(X, Y, m - 1, n));
     }
	    public static void dfs1(int node) {
	    	visited1[node] = true;
	    	for(int v :adjLists1[node]) {
	    		if(!visited1[v]) {
	    			dfs1(v);
	    		}
	    	}
	    	
	    }
	   static int maxSubsequenceSubstring(char[] X,char[] Y,int n,int m)
	    {
	        // Base Case
	        if (n==0 || m==0) return 0;
	        
	        // Calls on smaller inputs
	        
	        // if the last char of both strings are equal
	        if(X[n-1] == Y[m-1])
	        {
	            return  1 + maxSubsequenceSubstring(X,Y,n-1,m-1);
	        }
	        
	        // if the last char of both strings are not equal
	        else
	        {
	            return maxSubsequenceSubstring(X,Y,n-1,m);    
	        }
	    }
	    public static void dfs2(int node) {
	    	visited2[node] = true;
	    	for(int v :adjLists2[node]) {
	    		if(!visited2[v]) {
	    			dfs2(v);
	    		}
	    	}
	    }
	    static class Picture implements Comparable{
	    	char [][] pixels;
	    	int numOFOnes;
	    	int idx;
	    	public Picture(char [][] pixels, int numOfOnes, int idx) {
	    		this.pixels = pixels;
	    		this.numOFOnes = numOfOnes;
	    		this.idx = idx;
	    	}
			@Override
			public int compareTo(Object arg0) {
				Picture p = (Picture) arg0;
				return numOFOnes - p.numOFOnes;
			}
	    	
	    }
	    static  ArrayList<Integer> [] adjLists1;
	    static ArrayList<Integer> [] adjLists2;
	    static boolean []visited1;
	    static boolean [] visited2;
		static int [] arr ;
		static int d [] ;
		
	   static  HashSet<Long> hs = new HashSet<Long>();
	  
	public static int idxOf(String s,char c) {
		int idx = -2;
		for(int i = 0;i<s.length();i++) {
			if(s.charAt(i)==c) {
				return i;
			}
		}
		return idx;
	}
	static ArrayList<Long >start;
	static ArrayList<Long> end;
	public static void dfs (int idx) {
		can[idx] = true;
		for(int i = 0;i<start.size();i++) {
			if((start.get(i)<start.get(idx)&& end.get(i)>start.get(idx)||(start.get(i)<end.get(idx)&& end.get(i)>end.get(idx)))){
				if(!can[i]) {
				dfs(i);
			}}
		}
	}
	static boolean [] can ; 
	static int n;
	
	static int [] [] sol;
	static int [] g;
	public static void constructSol() {
		for(int i = 1;i<sol.length;i++) {
			for(int j = 1;j<10;j++) {
				if(g[i] == j) {
					sol[i][j] = sol[i-1][j]+1;
				}
				else {
					sol[i][j] = sol[i-1][j];
				}
			}
		}
	}
	public static void prod() {
		for(int i=1;i<g.length;i++) {
			int n = i;
		if(n<10) {
			g[ n] = n;
		    continue;
		}
		int prod = 1;
		while(n>0) {
			if(n%10!=0) {
				prod*= (n%10);
				
			}
			n/=10;
		}
		//System.out.println(prod);
		g[i] = g[prod];
	
	}}
	public static  boolean isPalindrome(String s) {
		
		for(int i = 0;i<=s.length()/2;i++) {
			if(s.charAt(i)!=s.charAt(s.length()-1-i)) {
				return false;
			}
		}
		return true;
	}
	public static long logBase2(long n) {
		long ans = 0;
		while(n>1) {
			ans ++;
			n/=2;
		}
		return ans;
	}
	public static double getmostLeft(ArrayList<Circle> list) {
	        double min = Double.MAX_VALUE;
	        for (Circle c: list) {
	            min = Math.min(min, c.x - c.r);
	        }
	        return min;
	    }
 
	   public static double getmostRight(ArrayList<Circle> list) {
	        double max = Double.MIN_VALUE;
	        for (Circle c: list) {
	            max = Math.max(max, c.x + c.r);
	        }
	        return max;
	    }
	static class Circle{
		double x ;
		double y ;
		double r;
		int id;
		public Circle(double x, double y, double r) {
			this.x = x;
			this.y = y;
			this.r = r;
			
		}
		public String toString () {
			return x +" "+y+" "+r;
		}
		public boolean intersect(Circle o) {
			double dist = Math.sqrt((y-o.y)*(y-o.y)+(x-o.x)*(x-o.x));
			if(dist<=r+o.r) {
				return true;
			}
			return false;
		}
		public  Circle combine( Circle o) {
			double dist = Math.sqrt((y-o.y)*(y-o.y)+(x-o.x)*(x-o.x));
		    if(Math.abs(r-o.r)>=dist) {
		    	if(r>=o.r) {
		    		return this;
		    	}
		    	else {
		    		return o;
		    	}
		    }
 
			double cx = (x+o.x)/2.0;
			double cy = (y+o.y)/2.0;
			double rad = (dist +r +this.r)/2.0;
			return new Circle (cx, cy, rad);
		}
	}
	static class Pair implements Comparable {
		long x;
		int y;
		public Pair (long x, int y) {
			this.x = x;
			this.y = y;
			
		}
		@Override
		public int compareTo(Object arg0) {
			Pair p = (Pair) arg0;
		return Long.compare(x, p.x);
		}
	}
	public static String solve (String s) {
		Stack <String> st = new Stack<String>();
		for(int i = 0;i<s.length();i++) {
			if(s.charAt(i)==']') {
				String toEncode = "";
				while(!st.isEmpty()&&!st.peek().equals("[")) {
					toEncode = st.pop()+ toEncode;
				}
				st.pop();
				String toPush = "";
				int freq = Integer.parseInt(st.pop());
				while(freq-->0) {
					toPush+=toEncode;
				}
				st.push(toPush);
			}
			else {
				st.push(s.charAt(i)+"");
			}
			
		}
		String res = "";
		while(!st.isEmpty()) {
			res = st.pop() +res;
		}
		return res;
	}
	static String alph = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

	static String s;
	static ArrayList <Integer> prime;
	 static void simpleSieve(int limit)
	    {   
	        // Create a boolean array "mark[0..n-1]" and initialize
	        // all entries of it as true. A value in mark[p] will
	        // finally be false if 'p' is Not a prime, else true.
	        boolean mark[] = new boolean[limit+1];
	         
	        for (int i = 0; i < mark.length; i++)
	            mark[i] = true;
	      
	        for (int p=2; p*p<limit; p++)
	        {
	            // If p is not changed, then it is a prime
	            if (mark[p] == true)
	            {
	                // Update all multiples of p
	                for (int i=p*p; i<limit; i+=p)
	                    mark[i] = false;
	            }
	        }
	      
	        // Print all prime numbers and store them in prime
	        for (int p=2; p<limit; p++)
	        {
	            if (mark[p] == true)
	            {
	                prime.add(p);
	               // System.out.print(p + "  ");
	            }
	        }
	    }
 
	 
	 public static long gcd (long a, long b ) {
		 if(b==0) {
			 return a;
		 }
		 else {
			 return gcd (b, a%b);
		 }
	 }
	 
 static class Scanner {
 		StringTokenizer st;
 		BufferedReader br;
  
 		public Scanner(InputStream s) {
 			br = new BufferedReader(new InputStreamReader(s));
 		}
        public Scanner(FileReader r) {
        	br = new BufferedReader(r);
        }
 		public boolean hasNext() {
 			// TODO Auto-generated method stub
 			return false;
 		}
  
 		public String next() throws IOException {
 			while (st == null || !st.hasMoreTokens())
 				st = new StringTokenizer(br.readLine());
 			return st.nextToken();
 		}
  
 		public int nextInt() throws IOException {
 			return Integer.parseInt(next());
 		}
  
 		public long nextLong() throws IOException {
 			return Long.parseLong(next());
 		}
  
 		public String nextLine() throws IOException {
 			return br.readLine();
 		}
  
 		public double nextDouble() throws IOException {
 			String x = next();
 			StringBuilder sb = new StringBuilder("0");
 			double res = 0, f = 1;
 			boolean dec = false, neg = false;
 			int start = 0;
 			if (x.charAt(0) == '-') {
 				neg = true;
 				start++;
 			}
 			for (int i = start; i < x.length(); i++)
 				if (x.charAt(i) == '.') {
 					res = Long.parseLong(sb.toString());
 					sb = new StringBuilder("0");
 					dec = true;
 				} else {
 					sb.append(x.charAt(i));
 					if (dec)
 						f *= 10;
 				}
 			res += Long.parseLong(sb.toString()) / f;
 			return res * (neg ? -1 : 1);
 		}
  
 		public boolean ready() throws IOException {
 			return br.ready();
 		}
  
 	}
}