Từ sau cái hôm làm bánh cho ông nguyenminhhai021009 ấy (xem lại bài Bán Bánh Dày), dù tôi kiếm được nhiều tiền nhưng lại bị mất kha khá khách (do bữa đó chỉ lo làm bánh cho ổng thôi mà). Mấy hôm sau, tôi có nhận được tin nhắn của ổng: "Hãy đến địa chỉ này gặp tôi" cùng với địa chỉ lạ. Tôi tới nơi thì, chao ôi, đó là một công ty lớn chuyên về ngành Toán học tên Mathtics. Tôi thấy ông Hải đứng ngoài cửa công ty rôi vẫy tay gọi tôi vào. Hóa ra, ông là Phó Giám Đốc của công ty này, vì nghe đồn tôi là người rất giỏi Toán nên tới thử tài. Vì tôi đã thỏa mãn được yêu cầu của ông lúc đó nên được gọi đến để phỏng vấn vào chức vụ Trợ lí của ngài Giám Đốc Công Ty stack_queue_4977. Tôi được đưa vào phòng của ngài, ngồi xuống ghế trước mặt ngài ấy. Ngài ấy bảo rằng ông rất ấn tượng về việc tôi hoàn thành thử thách của vị Phó Giám Đốc kia, và bảo nếu tôi trả lời chính xác \(Q\) câu hỏi toán mà ông sắp đưa cho tôi đây, thì ông sẽ tuyển dụng tôi ngay, khỏi bàn cãi. Tôi nhận đề, trên đề ghi như sau:

"Cho \(Q\) truy vấn, mỗi truy vấn gồm 2 số \(n\) và \(k\). Tính \(P^k_n\) \(\text{mod}\) \(10^{18}\) biết:"

"Ôi trời ơi khó quá!!!" - Tôi than ở trong đầu. Tôi chưa từng thấy bài thi nào khó như vậy. Tôi đang khổ sở thì nhớ ra các bạn coder LQDOJ. Các bạn ơi, các bạn hãy giải giúp tôi bài thi này để tôi được tuyển dụng nhé. Cảm ơn các bạn rất nhiều!!!!

Input

• Dòng 1 gồm số \(Q\).

• \(Q\) dòng tiếp theo, mỗi dòng gồm 2 số \(n\) và \(k\).

Output

• Với mỗi truy vấn, in ra \(P^k_n\) \(\text{mod}\) \(10^{18}\).

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(1\le Q \le 50000\).

• Subtask \(2\) (\(100\%\) số điểm): \(1 \le Q \le 150000\).

• Trong mỗi test:

  • 30% số test_case có \(1 \le n,k \le 10^5\).

  • 100% số test_case có \(1 \le n,k \le 10^{18}\).

Example

1
1 1

1

Note

Bài này đọc xong thấy có dễ ko mn :))

Phần giải thích cho mấy bạn chưa hiểu đề lắm:

• Dấu Sigma (hai dấu ở đầu biểu thức sau dấu = là dấu Sigma) là kí hiệu lấy tổng. Xem link này để hiểu rõ hơn.

• Kí hiệu \(C^j_k\) bạn thấy là kí hiệu toán học của tổ hợp. Xem link này để hiểu rõ hơn.