DCP-255: Parand()thesis Back to All Problems

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

Problem Setter:

Md. Nahidul Islam

Please login to submit solution to this problem.

Problem Limits

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

Problem Stats




# User Language Timing
01 nasif2587 Cpp14 0.00s
02 PKP_007 Cpp14 0.00s
03 sayedgkm Cpp14 0.00s
04 liar Cpp14 0.00s
05 feodorv Cpp14 0.00s
06 Dariwala Cpp14 0.01s
07 sumit1993 Cpp14 0.01s
08 akazad_cse13_ruet Cpp14 0.01s
09 SleepyBrain Cpp14 0.01s
10 Zeronfinity Cpp14 0.01s
11 mahbubcseju Cpp14 0.01s
12 dmehrab06 Cpp14 0.02s
13 habib_rahman Cpp14 0.02s
14 as_couple Cpp14 0.02s
15 shakil_ruet Cpp14 0.05s
16 ssavi Cpp14 0.09s
17 Morass Cpp14 0.12s
18 7Mahfuz Cpp14 0.14s
19 I_See_You Cpp14 0.14s
20 sahedsohel Cpp14 0.16s
21 tariqiitju Cpp14 0.26s
22 seyedssz Cpp14 0.37s
23 MRoy Cpp14 0.61s

Your feedback is our precious!

Or call +88 02 9853138 for support