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
Bình luận