Problem: Let n be an integer. Consider all permutations on integers 1 to n in lexicographic order, and concatenate them into one big sequence P. For example, if n = 3, then P = [1, 2, 3, 1, 3, 2, 2, 1, 3, 2, 3, 1, 3, 1, 2, 3, 2, 1]. The length of this sequence is n ⋅ n!.

Let 1 ≤ i ≤ j ≤ n ⋅ n! be a pair of indices. We call the sequence (P_i, P_{i+1}, ..., P_{j-1}, P_j) a subarray of P. 

You are given n. Find the number of distinct subarrays of P. Since this number may be large, output it modulo 998244353 (a prime number). 

Input

The only line contains one integer n (1 ≤ n ≤ 10^6), as described in the problem statement.

Output

Output a single integer — the number of distinct subarrays, modulo 998244353.

Examples

Input


2


Output


8


Input


10


Output


19210869

Note

In the first example, the sequence P = [1, 2, 2, 1]. It has eight distinct subarrays: [1], [2], [1, 2], [2, 1], [2, 2], [1, 2, 2], [2, 2, 1] and [1, 2, 2, 1]. 

Solution (in JAVA):

Solution:
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.stream.Stream;

/**
 * @author madi.sagimbekov
 */
public class C1091D {

    private static BufferedReader in;
    private static BufferedWriter out;

    private static List<Integer>[] list;
    private static int[] arr;
    private static int[][] dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    private static boolean[] used;

    private static long mod = 998244353;
    private static long[] f;
    private static long[] inv;

    public static void main(String[] args) throws IOException {
        open();

        int n = readInt();
        long sum = 0;

        f = new long[n + 1];
        inv = new long[n + 1];
        f[0] = 1;
        inv[0] = inverseEuler(f[0]);
        for (int i = 1; i <= n; i++) {
            f[i] = (f[i - 1] * i) % mod;
            inv[i] = inverseEuler(f[i]);
        }

        for (int i = 0; i < n; i++) {
            long c = C(n, i);
            long mul = (f[n - i] * (f[i] - 1)) % mod;
            mul = (mul * c) % mod;
            sum = (sum + mul) % mod;
        }

        sum += f[n];
        sum %= mod;

        out.write(sum +"\n");

        close();
    }

    private static long pow(long  a, long b) {
        long x = 1, y = a;
        while(b > 0)
        {
            if(b%2 == 1)
            {
                x=(x*y);
                if(x>mod) x%=mod;
            }
            y = (y*y);
            if(y>mod) y%=mod;
            b /= 2;
        }
        return x;
    }

    private static long inverseEuler(long n) {
        return pow(n, mod - 2);
    }

    private static long C(int n, int r) {
        long l;
        l=f[n];
        return (l*((inv[r] * inv[n-r]) % mod)) % mod;
    }

    private static int[] readInts() throws IOException {
        return Stream.of(in.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
    }

    private static int readInt() throws IOException {
        return Integer.parseInt(in.readLine());
    }

    private static long[] readLongs() throws IOException {
        return Stream.of(in.readLine().split(" ")).mapToLong(Long::parseLong).toArray();
    }

    private static long readLong() throws IOException {
        return Long.parseLong(in.readLine());
    }

    private static double[] readDoubles() throws IOException {
        return Stream.of(in.readLine().split(" ")).mapToDouble(Double::parseDouble).toArray();
    }

    private static double readDouble() throws IOException {
        return Double.parseDouble(in.readLine());
    }

    private static String readString() throws IOException {
        return in.readLine();
    }

    private static List<Integer>[] buildAdjacencyList(int n, int m) throws IOException {
        List<Integer>[] list = new ArrayList[n + 1];
        for (int i = 0; i <= n; i++) {
            list[i] = new ArrayList<>();
        }

        for (int i = 0; i < m; i++) {
            int[] e = readInts();
            list[e[0]].add(e[1]);
            list[e[1]].add(e[0]);
        }

        return list;
    }

    private static void open() {
        in = new BufferedReader(new InputStreamReader(System.in));
        out = new BufferedWriter(new OutputStreamWriter((System.out)));
    }

    private static void close() throws IOException {
        out.flush();
        out.close();
        in.close();
    }

}