同和创作矩阵 › ›博文归档› 技术博文归档 › 查看内容

21674_CountingProble

2022-5-16 18:20| 发布者: Hocassian| 查看: 19| 评论: 0|原作者: 肇庆学院ACM合集

摘要:

C:\Users\Administrator\Downloads\2019-10-12-10-14-4-89505748721300-Problem List-采集的数据-后羿采集器.html

Pro.ID

21674

Title

Counting Problem

Title链接

http://10.20.2.8/oj/exercise/problem?problem_id=21674

AC

Submit

Ratio

时间&空间限制

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)

描述

Yes. Counting problem comes again.

Given a chess board of N*N ( N ≤ 500 ), how many ways are there to put N queens on it so that no queen can attack another?

Luckily this is not the problem you should solve in this contest. Instead, we have a much easier one here.

Given a chess board of N*N ( N ≤ 500 ), how many ways are there to put 2*N queens on it so that there are exactly two queens in each row and each column?

To make it even easier, we will consider one way to be the same with another if it can be transformed to the other one by swapping rows and swapping columns.

输入

The first line of the input is an integer T indicating the number of cases.

Line 2..T+1 will contain an positive integer N ( N ≤ 500 ) each.

输出

Description

Yes. Counting problem comes again.

Given a chess board of N*N ( N ≤ 500 ), how many ways are there to put N queens on it so that no queen can attack another?

Luckily this is not the problem you should solve in this contest. Instead, we have a much easier one here.

Given a chess board of N*N ( N ≤ 500 ), how many ways are there to put 2*N queens on it so that there are exactly two queens in each row and each column?

To make it even easier, we will consider one way to be the same with another if it can be transformed to the other one by swapping rows and swapping columns.

Input

The first line of the input is an integer T indicating the number of cases.

Line 2..T+1 will contain an positive integer N ( N ≤ 500 ) each.

Output

T lines containing your counting results respectively.

For the number may be very large, you just have to output its module by 1000007.

Sample Input

3
2
5
4

Sample Output

1
2
2

Source

2008 Asia Chengdu Online