Mateo is extremely bored with his virtual classes. He is looking at the list of attendees in the class; there are a lot of people, a total of 2880. Mateo is thinking of his 3 favorite people in the class and wonders what is the probability that among the group of students there are 3 people who have the same birthday on the same day of the year and at the same time there are no more people who share birthdays, neither among themselves nor with the 3 people.
The next day, in his Probability exam, they ask him the exact same question, only they ask him to generalize the formula for $$$x$$$ people within a group of $$$n$$$. Mateo hates mathematics and that's why he didn't study probability for the ICPC, so he asks you to help him with this annoying exam question (considering that a year has 365 days).
The input consists of multiple test cases. The first line contains an integer $$$t$$$ $$$(1 \le t \le 10^3)$$$, the number of test cases.
Each test case consists of a single line containing two integers $$$n, x$$$ $$$(2 \le x \le n \le 10^{18})-$$$ the number of people in the group and how many people must have the same birthday.
For each test case, print the answer to the problem. It can be shown that the answer can be represented as an irreducible fraction $$$\frac{p}{q}$$$.
Print $$$pq^{-1}$$$ modulo $$$10^9 + 7$$$.
42 23 228 3100 99
882191787 839324457 542713201 259255172
