Bedan Contest #05 - G - Xếp xe

View as PDF

Submit solution


Points: 1500
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Author:
Problem type

Cho một bàn cờ với kích thước là n \times n, hãy đếm số lượng cách xếp n quân xe lên bàn cờ đó sao cho không có bất kì cặp xe nào tấn công nhau.

Input, Output and Scoring

Input
  • Số nguyên dương t (1 \le t \le 10^2).
  • t dòng tiếp theo, mỗi dòng gồm 1 số nguyên dương n (1 \le n \le 10^{18}).
Output
  • Với mỗi dòng, hãy in ra kết quả sau khi chia lấy dư cho 1234567891.

Test

Input
2
69
420
Output
1038218250
600140498

Comments

There are no comments at the moment.