Medium Math > Combinations and Permutations

**Prothoma** and **Diteeya** are twins in RUET. **29th February** is their birthday. This is a special day. It comes only in a **leap year**. They do always wear different dresses on their birthday and identical dresses over the year. So, most of the days they wear identical dresses. They had exactly **n** distinct dresses each having **two identical copy**. So,they had total 2n dresses. First n dresses for Prothoma and remaining set of n dresses for Diteeya. They asked their friend to find the number of ways in which they could wear 2n dresses over a year. But their friends are too weak at math to solve this problem. Your task is to help them. Now, you will be given the total number **n** and present year **m**. You have to find the number of ways in which they can wear those dresses over that year. Please, do not disappoint them. Note: Definition of leap year can be found here: https://en.wikipedia.org/wiki/Leap_year Input: ------ Input starts with an integer **T** (**1<=T<=50000**) denoting the number of test cases. Each case contains an integer **n** (**0 ≤ n ≤ 10^18**) and **m** ( **2000 ≤ m ≤ 10^18**) described before. The permutations of identical dresses are considered same. That is, if they wear identical dresses, then their order does not matter. Output: ------- For each case of input, output **Case X: Y**. Where X is the case number and Y is the desired result modulo **1000000007**. Sample Input ------------ 2 10 2002 20 2011 Sample Output ------------- Case 1: 196562168 Case 2: 939392971

Md. Abul Kalam Azad