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 will be 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. Its length is defined as the number of its elements, i.e., j - i + 1. Its sum is the sum of all its elements, i.e., ∑_{k=i}^j p_k. 

You are given n. Find the number of subarrays of p of length n having sum (n(n+1))/(2). 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 subarrays of length n having sum (n(n+1))/(2), modulo 998244353.

Examples

Input


3


Output


9


Input


4


Output


56


Input


10


Output


30052700

Note

In the first sample, there are 16 subarrays of length 3. In order of appearance, they are:

[1, 2, 3], [2, 3, 1], [3, 1, 3], [1, 3, 2], [3, 2, 2], [2, 2, 1], [2, 1, 3], [1, 3, 2], [3, 2, 3], [2, 3, 1], [3, 1, 3], [1, 3, 1], [3, 1, 2], [1, 2, 3], [2, 3, 2], [3, 2, 1]. 

Their sums are 6, 6, 7, 6, 7, 5, 6, 6, 8, 6, 7, 5, 6, 6, 7, 6. As (n(n+1))/(2) = 6, the answer is 9.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.NoSuchElementException;
import java.util.StringTokenizer;

public class Solution {
    private final static long MOD_BASE = 998244353L;
    private final int N;
    private final ModuloCalculator moduloCalculator = new ModuloCalculator(MOD_BASE);

    Solution(final int N) {
        this.N = N;
    }

    public static void main(String[] args) {
        final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        final InputReader reader = new InputReader(br);
        final int N = reader.nextInt();
        final Solution solver = new Solution(N);
        System.out.println(solver.solve());
    }

    long solve() {
        long factorial = 1;
        long badCuts = 0;
        for (int i = 2; i <= N; i++) {
            factorial = moduloCalculator.multiply(factorial, i);
            badCuts = moduloCalculator.add(moduloCalculator.multiply(badCuts, i), moduloCalculator.power(i - 1, 2));
        }
        final long totalCuts = moduloCalculator.subtract(moduloCalculator.multiply(N, factorial), N - 1);
        return moduloCalculator.subtract(totalCuts, badCuts);
    }
}

class InputReader {
    private final BufferedReader br;
    private StringTokenizer st;

    public InputReader(final BufferedReader br) {
        this.br = br;

    }

    public String next() {
        while (st == null || !st.hasMoreElements()) {
            try {
                final String line = br.readLine();
                if (line == null) {
                    throw new NoSuchElementException();
                }
                st = new StringTokenizer(line);
            } catch (final IOException e) {
                e.printStackTrace();
            }
        }
        return st.nextToken();
    }

    public int nextInt() {
        return Integer.parseInt(next());
    }

    // Assumes chars are not concatenated
    public char nextChar() {
        final String str = next();
        assert str.length() == 1;
        return str.charAt(0);
    }

    public long nextLong() {
        return Long.parseLong(next());
    }

    public double nextDouble() {
        return Double.parseDouble(next());
    }
}

class ModuloCalculator {
    private final long base;
    private static final long NO_BASE = 0;

    public ModuloCalculator(final long base) {
        assert base >= 0;
        this.base = base;
    }

    public static ModuloCalculator getWithoutMod() {
        return new ModuloCalculator(NO_BASE);
    }

    public long getInverse(final long y) {
        assert base > 0;
        final long x = normalize(y);
        assert x > 0;
        final BezoutRepr bezoutRepr = MathUtils.getBezoutRepr(x, base);
        assert bezoutRepr.getGcd() == 1;
        return normalize(bezoutRepr.getCoeffSmall());
    }

    public long add(final long x, final long y) {
        return normalize(normalize(x) + normalize(y));
    }

    public long subtract(final long x, final long y) {
        return add(x, -y);
    }

    public long multiply(final long x, final long y) {
        return normalize(normalize(x) * normalize(y));
    }

    public long getExactQuotient(final long x, final long y) {
        if (base != NO_BASE) {
            return multiply(x, getInverse(y));
        }
        assert x % y == 0;
        return x / y;
    }

    public long power(final long _base, final int pow) {
        return _power(normalize(_base), pow);
    }

    private long _power(final long _base, final long pow) {
        if (pow == 0) {
            return 1;
        }
        assert pow > 0;
        long partialResult = _power(_base, pow / 2);
        partialResult = normalize(partialResult * partialResult);
        if (pow % 2 == 1) {
            partialResult = normalize(partialResult * _base);
        }
        return partialResult;
    }

    /**
     * @return a value b/w 0 <= ret < b
     */
    public long normalize(final long y) {
        if (base == 0) {
            return y;
        }
        long x = y % base;
        if (x < 0) {
            x = base + x;
        }
        return x;
    }
}

class MathUtils {
    /**
     * Assumes x <= y
     * @param smaller - >= 0
     * @param larger  - >= x
     */
    public static BezoutRepr getBezoutRepr(final long smaller, final long larger) {
        assert smaller >= 0;
        assert smaller <= larger;
        if (smaller == 0) {
            return new BezoutRepr(1, 1, larger, 1);
        }
        final long r = larger % smaller;
        final long q = larger / smaller;
        // gcd(x, y): y = q1*x + r1 => r1 = y - q1*x
        // a * smaller(r1) + b * larger(x) = gcd
        // => a * (y - q1*x) + b * x = gcd
        // => (b - a * q1) * x + a * y = gcd
        // => a' = b - a * q1
        // => b' = a
        // gcd(r, x): x = q2*r + r2 => gcd = r2 = x - q2*r1 (1, -q2)
        final BezoutRepr child = getBezoutRepr(r, smaller);
        long smallCoeff = child.getCoeffLarge() - child.getCoeffSmall() * q;
        final long gcd = child.getGcd();
        return new BezoutRepr(smallCoeff, child.getCoeffSmall(), gcd, child.getNumCalls() + 1);
    }
}

/**
 * The time complexity of this class is O(NlgN) if mod is involved, and O(N) if mod is not involved.
 * The log N factor in case of mod comes from inverses
 * Space complexity is O(N) in both cases
 */
class BinomialCoefficientsForN {
    private final int N;
    private final long[] coeffs;
    private final ModuloCalculator mod;

    public BinomialCoefficientsForN(final int N, final ModuloCalculator mod) {
        assert N > 0;
        this.N = N;
        this.mod = mod;
        this.coeffs = new long[N / 2 + 1];
        compute();
    }

    private void compute() {
        coeffs[0] = 1;
        for (int i = 1; i <= N / 2; i++) {
            coeffs[i] = mod.getExactQuotient(mod.multiply(coeffs[i - 1], N - i + 1), i);
        }
    }

    public long getCoefficient(final int r) {
        assert r >= 0;
        assert r <= N;
        if (r > N / 2) {
            return coeffs[N - r];
        }
        return coeffs[r];
    }
}

class BezoutRepr {
    private final long coeffSmall;
    private final long coeffLarge;
    private final long gcd;
    private final int numCalls;

    public BezoutRepr(final long coeffSmall, final long coeffLarge, final long gcd, final int numCalls) {
        this.coeffSmall = coeffSmall;
        this.coeffLarge = coeffLarge;
        this.gcd = gcd;
        this.numCalls = numCalls;
    }

    public long getCoeffSmall() {
        return coeffSmall;
    }

    public long getCoeffLarge() {
        return coeffLarge;
    }

    public long getGcd() {
        return gcd;
    }

    public int getNumCalls() {
        return numCalls;
    }

    @Override
    public String toString() {
        return "BezoutRepr{" + "coeffSmall=" + coeffSmall + ", coeffLarge=" + coeffLarge + ", gcd=" + gcd
                + ", numCalls=" + numCalls + '}';
    }
}
