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 \cdot n!$.

Let $1 \leq i \leq j \leq n \cdot n!$ be a pair of indices. We call the sequence $(p_i, p_{i+1}, \dots, 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., $\sum_{k=i}^j p_k$. 

You are given $n$. Find the number of subarrays of $p$ of length $n$ having sum $\frac{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 \leq n \leq 10^6$), as described in the problem statement.


-----Output-----

Output a single integer — the number of subarrays of length $n$ having sum $\frac{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 $\frac{n(n+1)}{2} = 6$, the answer is $9$.

Difficulty: interview

Starter code:

Solutions:
MOD = 998244353

list_size = 1000001

f_list = [1] * list_size
f_r_list = [1] * list_size

for i in range(list_size - 1):
	f_list[i + 1] = int((f_list[i] * (i + 2)) % MOD)

def power(n, x):
	if x == 1:
		return n
	elif x % 2 == 0:
		return power(int((n * n) % MOD), int(x / 2))
	else:
		return int((n * power(n, x - 1)) % MOD)

f_r_list[-1] = power(f_list[-1], MOD - 2)

for i in range(2, list_size + 1):
	f_r_list[-i] = int((f_r_list[-i + 1] * (list_size + 2 - i)) % MOD)

def comb(n, r):
	if n < r:
		return 0
	elif n == 0 or r == 0 or n == r:
		return 1
	else:
		return (((f_list[n - 1] * f_r_list[n - r - 1]) % MOD) * f_r_list[r - 1]) % MOD 

n = int(input())
ans = f_list[n-1]
for i in range(2, n):
	ans = (ans + comb(n, i) * (f_list[i-1] - 1) * f_list[n-i-1]) % MOD
print(ans)

import math
n = int(input())

mod = 998244353

F = [1, 1]
f = 1
for i in range(2,n+1):
    f*=i
    f%=mod
    F.append(f)

ret = 1
for i in range(1, n+1):
    ret=ret*i-i+F[i]
    ret%=mod

print(ret)


n = int(input())
mass = [n]
mass1 = [1]
for i in range(2, n + 1):
    mass1.append((mass1[-1] * i) % 998244353)
for i in range(n - 1, 0, -1):
    mass.append((mass[-1] * i) % 998244353)
summ = mass1[-1]
mass.reverse()
for i in range(n - 1):
    summ += mass[i + 1] * (mass1[i] - 1)
    summ % 998244353
print(summ % 998244353)

#!/usr/bin/env python
# coding: utf-8

# In[35]:

#import time

n=int(input())


# In[36]:


# In[37]:


fac=1
#t1 = time.time()

for i in range(2,n+1):
    fac=fac*i%998244353

#t2 = time.time()


total=(n-1)*fac%998244353
dsum=0
diff=1
for i in range(0,n-2):
    
    diff=diff*(n-i)%998244353
    #print(diff)    
    dsum+=diff%998244353    

answer=(total-dsum)%998244353
# In[38]:

#t3 = time.time()

#print(t3-t2,t2-t1)

if n==1:
    print(1)
else:    
    print(answer)


# In[31]:


n = int(input())
ans = 1
frac = 1
m = 998244353
for i in range(2, n + 1):
    ans = (((ans + frac - 1) % m) * i) % m
    frac = (frac * i) % m
print(ans)

import sys
import math


MAX = 1000010
MOD = 998244353 


def main():
    ar = [1 for _ in range(MAX)]
    fact = [1 for _ in range(MAX)]
    
    for n in range(2, MAX):
        fact[n] = fact[n - 1] * n % MOD
    
    for n in range(2, MAX):
        ar[n] = ((ar[n - 1] - 1) * n + fact[n]) % MOD
    
    n = int(input())
    print(ar[n])
    
    
def __starting_point():
	main() 

__starting_point()

n = int(input())
last = n - 1
for i in range(3, n + 2):
    last = (last * (i - 1) - 1) % 998244353
print(last + 1)

res = 0
n = int(input())
f = 1
s = 0
for i in range(n, 1, -1):
    f = (f * i) % 998244353
    s = (s + f) % 998244353
print((f * n - s) % 998244353) 


P = 998244353

n = int(input().strip())

sub_sum = 0
curr_num = 1
for idx in range(n-1):
    curr_num = ((curr_num * (n - idx)) % P)
    sub_sum = ((sub_sum + curr_num) % P)

add_num = ((curr_num * n) % P)

final = ((add_num - sub_sum) % P)
print(final)

t = int(input())
res = t
i = 2
while(i<=t):
    res = (res-1)*i%998244353  
    i+=1
print(res)

n = int(input())
M = 998244353

ans = 1

fac = 1
phi = 1

for q in range(n, 2, -1):
	fac *= q
	fac %= M
	phi += fac
	phi %= M

fac *= 2
fac %= M

ans += fac*(n-1)
ans %= M

ans += M - phi
ans %= M

if n == 1:
	ans = 1

print(ans)

n = int(input())
mod = 998244353
rev = []
cur = 1
s = 0
for i in range(n, 0, -1):
	cur *= i
	tmp = cur - s
	s += tmp
	s %= mod
	cur %= mod
	rev.append(tmp % mod)
# print(rev)
ans = 1
for i in range(1, n + 1):
	ans *= i
	ans %= mod
for i in range(1, n - 1):
	ans += i * rev[i]
	ans %= mod
print(ans)

n = int(input())
dd = 998244353
dp = [(1,0), (1, 0), (2, 0), (6, 3)]
if n == 1:
    print(1)
    return
elif n == 2:
    print(2)
    return

for i in range(4, n+1):
    np = (dp[-1][0]*i, i*(dp[-1][0]-1) + i*(dp[-1][1]))
    np = (np[0] % dd, np[1] % dd)
    dp.append(np)

print((dp[-1][0] + dp[-1][1]) % dd)



# -*- coding: utf-8 -*-
"""
Spyder Editor

This is a temporary script file.
"""
mod=998244353
n=int(input())
a=[]
i=1
a.append(0)
a.append(n)
ans=n
for i in range(1,n):
    ans=((ans%mod)*(n-i))%mod
    a.append(ans)
#print(*a)
ans=0
for i in a:
    ans=(ans%mod+a[-1]%mod-i%mod)%mod
print(ans)

def factorial_mod(n, mod):
    ans = 1
    for i in range(1, n + 1):
        ans = (ans * i) % mod
    return ans

def solve(n):
    if n == 1:
        return 1
    elif n == 2:
        return 2
    mod = 998244353
    len_metaseq = factorial_mod(n, mod)
    ans = (
        ((n - 1) + (n - 2)) *
        len_metaseq *
        499122177 # modinv(2, mod)
    ) % mod
    error = 0
    for curr in range(4, n + 1):
        error = ((error + 1) * curr) % mod
    return (ans - error) % mod

n = int(input())
print(solve(n))

MOD = 998244353
n = int(input())
if n < 3:
    print(n)
else:
    mxm = 9
    m = 3
    mf = 6
    for _ in range(n - 3):
        m += 1
        mxm = (mxm + 1) * m
        mxm %= MOD
        mf *= m
        mf %= MOD
    print((n * mf - mxm) % MOD)


MOD = 998244353
I = lambda:list(map(int,input().split()))

n, = I()

s = [1, 2]
for i in range(3, 10**6+1):
    s.append(((s[-1] + 1)*i)%MOD)

f = 1
l = []
for i in range(1, 10**6+1):
    l.append((f*i)%MOD)
    f = (f*(i+1))%MOD
    # print(f)
# print(l)
# print(s)
n -= 1
if n == 0:
    print(1)
    return
print((l[n] - s[n])%MOD)
# print()


m = 998244353
n = int(input())
f = [0 for i in range(n+1)]
ff = [0 for i in range(n+1)]
f[1] = 1
ff[n] = n
for i in range(2,n+1):
    f[i] = (f[i-1]%m * i%m) %m

for i in range(n-1,1,-1):
    ff[i] =(ff[i+1]%m * i%m) %m

ans = (f[n]%m * n%m)%m

for i in range(2,n+1,1):
    ans = (ans%m + (-1 * ff[i]%m)%m)%m
print(ans)



def read_nums():
    return [int(x) for x in input().split()]


def main():
    n, = read_nums()
    cur_res = 1
    factorial = 1
    for i in range(2, n+1):
        factorial = (factorial * i) % 998244353
        cur_res = ((cur_res - 1) * i + factorial) % 998244353
    print(cur_res)


def __starting_point():
    main()

__starting_point()

MOD = 998244353
fac=[1]*1000007
for i in range(2,1000001):
	fac[i]=fac[i-1]*i
	fac[i]%=MOD
dp=[0]*1000007
for i in range(3, 1000001):
	dp[i]=(dp[i-1]+fac[i-1]-1)*i
	dp[i]%=MOD
#print(dp[1:11])

n=int(input())

ans=(fac[n]+dp[n])%MOD
print(ans)


n = int(input())

fact = [0,1]
for i in range(2,n+1):
    fact.append((fact[-1]*i)% 998244353)

ans = [0,1]

for i in range(2,n+1):
    ans.append((fact[i]+i*ans[-1]-i)%998244353)
    
print(ans[-1])

def iterative_egcd(a, b):
    x, y, u, v = 0, 1, 1, 0
    while a != 0:
        q, r = b // a, b % a;
        m, n = x - u * q, y - v * q  # use x//y for floor "floor division"
        b, a, x, y, u, v = a, r, u, v, m, n
    return b, x, y


def modinv(a, m):
    g, x, y = iterative_egcd(a, m)
    if g != 1:
        return None
    else:
        return x % m

def factorialMod(n, modulus):
    ans=1
    if n <= modulus//2:
        #calculate the factorial normally (right argument of range() is exclusive)
        for i in range(1,n+1):
            ans = (ans * i) % modulus
    else:
        #Fancypants method for large n
        for i in range(1,modulus-n):
            ans = (ans * i) % modulus
        ans = modinv(ans, modulus)

        #Since m is an odd-prime, (-1)^(m-n) = -1 if n is even, +1 if n is odd
        if n % 2 == 0:
            ans = -1*ans + modulus
    return ans % modulus


n = int(input())
if n == 1:
    print(1)
else:
    m = 998244353
    ans = ((n - 1) * factorialMod(n, m)) % m
    k = 0
    for i in range(3, n + 1):
        k = ((k + 1) * i) % m
    print((ans - k) % m)

M = 998244353


def fact(n):
    ans = 1
    for i in range(2, n + 1):
        ans *= i
        ans %= M
    return ans


n = int(input())


x = fact(n)
ans = x - n
k = n
for i in range(1, n + 1):
    ans += x - k * (n - i)
    ans %= M
    k *= (n - i)
    k %= M
print(ans)


n = int(input())

M = 998244353
f = n
s = n
for i in range(1, n):
    f = f * (n - i)
    x = n - i - 1
    y = (f * x) // (x + 1)
    s += (i + 1) * y
    s %= M
    f %= M
print(s % M)