AT_agc076_a [AGC076A] Hamming-Distant Arrays

You are given an integer $ N $ . For length- $ N^2 $ integer sequences $ a $ and $ b $ consisting of integers between $ 1 $ and $ N $ (inclusive), we define their distance $ d(a,b) $ as follows: - $ d(a,b)= $ "the number of indices $ i $ ( $ 1 \leq i \leq N^2 $ ) such that $ a_i \neq b_i $ ." Now, you will create $ N $ length- $ N^2 $ integer sequences consisting of integers between $ 1 $ and $ N $ , and denote them as $ x_1,x_2,\cdots,x_N $ (their order also matters). Find the number, modulo $ 998244353 $ , of instances of $ (x_1,x_2,\cdots,x_N) $ satisfying the following condition. - For any length- $ N^2 $ integer sequence $ y $ consisting of integers between $ 1 $ and $ N $ , there exists some $ 1 \leq i \leq N $ such that $ d(x_i,y) \geq N^2-N $ .

The input is given from Standard Input in the following format: > $ N $

Output the answer.

### Sample Explanation 1 For example, $ (x_1,x_2)=((1,1,2,2),(1,2,1,2)) $ does not satisfy the condition, because if $ y=(1,1,1,2) $ , then $ d(x_1,y)=1,d(x_2,y)=1 $ . On the other hand, $ (x_1,x_2)=((1,1,1,1),(2,2,2,2)) $ satisfies the condition. There are $ 80 $ instances of $ (x_1,x_2) $ that satisfy the condition. ### Constraints - $ 1 \leq N \leq 50 $ - All input values are integers.