Problem: Kavi has 2n points lying on the OX axis, i-th of which is located at x = i.

Kavi considers all ways to split these 2n points into n pairs. Among those, he is interested in good pairings, which are defined as follows:

Consider n segments with ends at the points in correspondent pairs. The pairing is called good, if for every 2 different segments A and B among those, at least one of the following holds:

  * One of the segments A and B lies completely inside the other. 
  * A and B have the same length. 



Consider the following example:

<image>

A is a good pairing since the red segment lies completely inside the blue segment.

B is a good pairing since the red and the blue segment have the same length.

C is not a good pairing since none of the red or blue segments lies inside the other, neither do they have the same size.

Kavi is interested in the number of good pairings, so he wants you to find it for him. As the result can be large, find this number modulo 998244353.

Two pairings are called different, if some two points are in one pair in some pairing and in different pairs in another.

Input

The single line of the input contains a single integer n (1≤ n ≤ 10^6).

Output

Print the number of good pairings modulo 998244353.

Examples

Input


1


Output


1

Input


2


Output


3

Input


3


Output


6

Input


100


Output


688750769

Note

The good pairings for the second example are: 

<image>

In the third example, the good pairings are: 

<image>

Solution (in CPP):

Solution:
/* Utkrisht Sikka */
#include <iostream>
#include <cmath>
#include <vector>
#include <queue>
#include<set>
#include<bitset>
#include<stack>
#include<unordered_set>
#include<map>
#include <algorithm>
#include <unordered_map>
#include <fstream>
#include <tuple>
#include <cstring>
#include<cstdlib>
#include<ctime>
#include<chrono>
#include <climits>
#include <iomanip>
#include <cfloat>
#define mp make_pair
#define mt make_pair
#define pb push_back
#define se second
#define fi first
#define file
#define PI 3.141592653589793238462
#define go(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define goa(i,p,n) for(int i=p;i<=(n);++i)  
#define god(i,p,n) for(int i=p;i>=(n);--i)
using namespace std;
using namespace std::chrono;  
typedef long long  ll;
typedef unsigned long long ull;
typedef long double lld;


typedef pair<int, int> pii;
typedef vector<int> vi;
const ll M=998244353LL;

//=======================================================================================================
template <class T> ll maxpower(T a , T b){
  ll ans = 0;
  while(a > 0 && a % b == 0){
    ans++;
    a /= b;
  }
  return ans;
}
template <class T>
void debug(T ar[], int n){
  cout << "deb\n";
  goa(i, 1, n){
    cout << ar[i] << " ";
  }
  cout << "\n";


}

template <class T> T egcd(T a , T b , T &x , T &y){T gcd , xt , yt;if(a == 0){gcd = b;x = 0 , y = 1;}else {gcd = egcd(b % a , a , xt , yt);x = yt - (b/a)*xt; y = xt;}return gcd;}
template <class T> T expo(T base , T exp , T mod){T res = 1;base = base % mod;while (exp > 0){if (exp & 1)res = (res*base) % mod;exp = exp>>1;base = (base*base) % mod;}return res;}
template <class T> T modinv(T a , T mod){T x , y; egcd<T>(a , mod , x , y);while(x < 0) x += mod; while(x >= mod) x -= mod; return x;}
template <class T> T modinvfermat(T a , T mod){return expo<T>(a , mod - 2 , mod);}

class node{
    public:
int f1;
node *left;
node *right;
node( int f1){
this->f1 = f1;
this->left = nullptr;
this->right = nullptr;
}

};
ll gcd(ll a, ll b) {
  if (b > a) {return gcd(b, a);}
  if (b == 0) {return a;}
  return gcd(b, a % b);
}
  
void swap(int &a, int &b) {
  int t = a; a = b; b = t;
}
struct compare{// for priority queue
bool operator()(node const& i1, node const& i2)
{
    return (i1.f1 > i2.f1);
}
};
  struct compareinc{// for multiset  first element will be max element
bool operator()( node* const& i1,  node* const& i2)
const {
    return (i1->f1 >= i2->f1);
}
};
struct comparedec{// for priority queue top() will be min element
bool operator()(int  i1, int  i2)
{
    return (i1 > i2);
}
};
bool IsApproximatelyEqual(double x, double y, double epsilon){
            // """Returns True if y is within relative or absolute 'epsilon' of x.

            // By default, 'epsilon' is 1e-6.
            // """
            // # Check absolute precision.
            if ((-epsilon <= (x - y)) && ((x-y) <= epsilon))
              return true;

            // # Is x or y too close to zero?
            if (((-epsilon <= x) && (x <= epsilon)) || ((-epsilon <= y) &&(y <= epsilon)))
              return false;

            // # Check relative precision.
            return ((-epsilon <= ((x - y) / x)) && (((x - y) / x) <= epsilon)) ||
                ((-epsilon <= ((x - y) / y)) &&(((x - y) / y) <= epsilon));
}
// bool compareInterval(node i1, node i2) //for sort
// { 
    // return (i1.f1 < i2.f1); 
// } 
bool compareInterval(int i1, int i2) //for sorting in increasing order
{ 
    return (i1 < i2); 
} 

ll getlen(char *s){
  ll k = 0;
  while(*s != '\0'){
    s += 1;
    k += 1;
  }
    return k;

}
//========================================================================================
 ll dp[1000009];
 ll sumdp[1000009];

 //https://www.geeksforgeeks.org/count-divisors-n-on13/
void SieveOfEratosthenes(int n, bool prime[],
                         bool primesquare[], int a[])
{
    // Create a boolean array "prime[0..n]" and
    // initialize all entries it as true. A value
    // in prime[i] will finally be false if i is
    // Not a prime, else true.
    for (int i = 2; i <= n; i++)
        prime[i] = true;
 
    // Create a boolean array "primesquare[0..n*n+1]"
    // and initialize all entries it as false. A value
    // in squareprime[i] will finally be true if i is
    // square of prime, else false.
    for (int i = 0; i <= (n  ); i++)
        primesquare[i] = false;
 
    // 1 is not a prime number
    prime[1] = false;
    // cerr << "stage1\n";
    for (int p = 2; p * p <= n; p++) {
        // If prime[p] is not changed, then
        // it is a prime
        if (prime[p] == true) {
            // Update all multiples of p
            for (int i = p * 2; i <= n; i += p)
                prime[i] = false;
        }
    }
     // cerr << "stage2\n";

    int j = 0;
    for (int p = 2; p <= n; p++) {
      // cerr << p << ":p\n";
        if (prime[p]) {
           // cerr << prime[p] << ":prime[p]\n";
            // Storing primes in an array
            a[j] = p;
            
            // Update value in primesquare[p*p],
            // if p is prime.
            if(p <= sqrt(n))
            primesquare[p * p] = true;
            j++;
        }
    }
        // cerr << "stage3\n";

}
 
// Function to count divisors
int countDivisors(int n, bool prime[],
                         bool primesquare[], int a[])
{
     // cerr << n << ":initially\n";
    // If number is 1, then it will have only 1
    // as a factor. So, total factors will be 1.
    if (n == 1)
        return 1;
 
  
 
    // Calling SieveOfEratosthenes to store prime
    // factors of n and to store square of prime
    // factors of n
   
 
    // ans will contain total number of distinct
    // divisors
    int ans = 1;
 
    // Loop for counting factors of n
    for (int i = 0;; i++) {
        // a[i] is not less than cube root n
        if (a[i] * a[i] * a[i] > n)
            break;
 
        // Calculating power of a[i] in n.
        int cnt = 1; // cnt is power of prime a[i] in n.
        while (n % a[i] == 0) // if a[i] is a factor of n
        {
            n = n / a[i];
            cnt = cnt + 1; // incrementing power
        }
 
        // Calculating the number of divisors
        // If n = a^p * b^q then total divisors of n
        // are (p+1)*(q+1)
        ans = ans * cnt;
    }
 
    // if a[i] is greater than cube root of n
 // cerr << ans << ":till\n";
    // First case
    if (prime[n])
        ans = ans * 2;
 
    // Second case
    else if (primesquare[n])
        ans = ans * 3;
 
    // Third case
      
    else if (n != 1)
        ans = ans * 4;
 
    return ans; // Total divisors
}
//------------------
 bool prime[1000000 + 1], primesquare[1000000 + 1];

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
  int t = 1, n = 100000;
  // cin >> t;
   
 
    int a[100000]; // for storing primes upto n
 SieveOfEratosthenes(1000000, prime, primesquare, a);
 // cerr << "after seive\n";
  auto start = high_resolution_clock::now();
  while(t-- > 0){
    cin >> n;
    dp[0] = 1;
    dp[1] = 1;
    
    sumdp[0] = 1;
    sumdp[1] = sumdp[1-1]+dp[1];
    for(int  i = 2; i<= n; i++){

      dp[i] = (sumdp[i-1] + countDivisors(i,prime, primesquare, a) - 1 )%M;
      sumdp[i] = (sumdp[i-1] + dp[i])%M;
    }
    cout << dp[n] ;
    // time: 
  }
  auto stop = high_resolution_clock::now();
  auto duration = duration_cast<microseconds>(stop - start);
  cerr << "Time: " << duration.count()/1000000.0 <<"s"<< endl;
 
}