/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 700 点
問題文
整数 N が与えられます． 1 以上 N 以下の整数からなる長さ N^2 の整数列 a,b に対し，その距離 d(a,b) を次のように定義します．
- d(a,b)=「a_i \neq b_i を満たす i (1 \leq i \leq N^2) の個数」
今から，1 以上 N 以下の整数からなる長さ N^2 の整数列を N 個作り，それらを x_1,x_2,\cdots,x_N とおきます（順番も区別します）． 以下の条件を満たす (x_1,x_2,\cdots,x_N) の個数を 998244353 で割ったあまりを求めてください．
- 1 以上 N 以下の整数からなる長さ N^2 の整数列 y をどのようにとっても，ある 1 \leq i \leq N が存在し，d(x_i,y) \geq N^2-N を満たす．
制約
- 1 \leq N \leq 50
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる．
N
出力
答えを出力せよ．
入力例 1
2
出力例 1
80
例えば，(x_1,x_2)=((1,1,2,2),(1,2,1,2)) は条件を満たしません． y=(1,1,1,2) とすると，d(x_1,y)=1,d(x_2,y)=1 となるためです．
一方，(x_1,x_2)=((1,1,1,1),(2,2,2,2)) は条件を満たします．
条件を満たす (x_1,x_2) は 80 通りあります．
入力例 2
3
出力例 2
597965565
入力例 3
10
出力例 3
241191911
Score : 700 points
Problem Statement
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.
Constraints
- 1 \leq N \leq 50
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N
Output
Output the answer.
Sample Input 1
2
Sample Output 1
80
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.
Sample Input 2
3
Sample Output 2
597965565
Sample Input 3
10
Sample Output 3
241191911