# DCP-230: Twin Back to All Problems

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

### Problem Limits

 Language Time Limit (seconds) C 1.00 C++ 1.00 C++14 1.00 C# 2.00 Go 2.00 Java 2.00 JavaScript 2.00 Objective-C 2.00 Perl 2.00 PHP 2.00 Python 2.00 Python3 2.00 Ruby 2.00 VB.Net 2.00

# 29/283

Solve/Submission

### Ranking

# User Language Timing
01 rayhan50001 Cpp14 0.02s
02 Morass Cpp14 0.02s
03 Robbinb1993 Cpp14 0.02s
04 onucsecu Cpp14 0.03s
05 feodorv Cpp14 0.03s
06 dmehrab06 Cpp14 0.03s
07 farhanhasin Cpp14 0.03s
08 ssavi Cpp14 0.04s
09 phoenix71 Cpp14 0.04s
11 Double_O Cpp14 0.10s
12 khatribiru Cpp14 0.17s
13 MRITuhin Cpp14 0.17s
14 swapnilsaha Cpp14 0.19s
15 tariqiitju Cpp14 0.26s
16 ovis96 Cpp14 0.26s
17 deder Cpp14 0.42s
Feedback