Hard Math > Counting

![Tom and Jerry][1] Tom and Jerry are two famous programmers. Jerry practices hard all day long, but on the other hand Tom always tries to find shortcuts. We all know there are no shortcuts to success. But somehow until this day, Tom managed to be successful. This misjudgment demotivates Jerry to concentrate his programming practice. That’s why, he finally makes a decision to reveal the true self of Tom. Jerry challenges Tom to write a code that generates valid parenthesis expressions. Rather than writing a good code, Tom copies a code from the internet and shows to Jerry. Unfortunately, that code generates random parenthesis expressions without checking any validity at all. Tom’s code takes a number **N** and generates an expression of parenthesis consist of **N pairs** randomly. For example, some of the randomly generated **2 pairs** parenthesis expression can be **((((, ()((, ))(), (()),** … etc. As you can see some of them are valid and others are not. Now, the critical moment has come and Jerry will give the input **N** to Tom’s code. But he fears, what if he loses the challenge? But as a good programmer, you know that Jerry needs to be afraid a little, right? So, as a helping hand, you will calculate the probability of winning the challenge by Tom for a given value of **N** and show it to Jerry that how poor Tom’s code is. This will enhance the confidence of Jerry of course! **More specifically,** what is the probability of getting a valid **N pairs** parenthesis expression generated randomly. This probability can be written as an **irreducible** fraction **A / B**. Your task is to find the values of **A** and **B** (Jerry does not like to deal with floating point numbers). If **V** is a valid configuration then, **VV** and **(V)** are also valid. For example, **V=()**. Input: ------ Input starts with an integer **T (<=10)**, denoting the number of test cases. Each case contains an integer **N (1 ≤ N ≤ 10000)** denoting the **number of parenthesis pairs** in the expression. Output: ------- For each case, print the case number and the desired probability. See the samples for exact formatting. If the desired probability is **P**, then print two numbers **A** and **B** where **P = A / B** and **A** and **B** are coprime **(A >= 0, B >= 1, gcd(A, B) = 1)**. Since these numbers may be too large, print them modulo **10^9 + 7**. Note that **A** and **B** must be coprime before their remainders modulo **10^9 + 7** are taken. Sample Input ------------ 2 1 2 Sample Output ------------- Case 1: 1 4 Case 2: 1 8 [1]: https://s3-ap-southeast-1.amazonaws.com/devskillimagestorage/questionimages/513575f6-8391-c79f-010f-08d44ec324d4_368d4cf0016d4cfaa53725e3fd345d89_W650xH487.jpg

Md. Nahidul Islam