Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Game Show

By fsshakkhor · Limits 2s, 1.0 GB

Alex is participating in a game show. Mr. Phil is the host of the game. Alex is provided with an array containing N distinct integers from 1 to N. Mr. Phil has the same copy of the array. There are two phases of the game.

Phase 1: A wheel is rolled. The wheel will show a random integer in between 0 and N. Let the number be X. Then X integers will be randomly selected from Alex's array and removed. Now Mr. Phil's array contains N integers, but Alex's array contains N - X integers.

Phase 2: Again the wheel is rolled. This time the wheel will show a random integer between 0 and N - X. Let the number be K. Mr. Phil will randomly pick K integers from his array. If Alex's array contains all these K integers that were selected by Mr. Phil, then Alex wins.

Here is a simulation of the game.

Suppose N = 3. Initially Alex's array is [1 2 3] and Mr. Phil's array is [1 2 3]

In phase 1, the wheel shows X = 1. So 1 integer will be removed from Alex's array. Let it be number 2. So currently Alex's array is [1 3] and Mr. Phil's array is [1 2 3].

In phase 2, the wheel shows K = 2. So Mr. Phil will randomly pick 2 integers from his array.

If he picks [1 3], Alex wins.
If he picks [1 2] or [2 3], Alex loses.

You have to find the probability of Alex winning the game. The probability can be written in form PQ\frac{P}{Q}, where PP and QQ are relatively prime integers and Q0Q \neq 0 mod 998244353998244353 . You have to print the value of (PQ1)(P Q ^{-1}) mod 998244353998244353.


First line contains an integer T (1 ≤ T ≤ 5000) denoting the number of test cases.

Each of the next T lines contain an integer N (1 ≤ N ≤ 30000000).


For each test case, output the value of (PQ1)(P Q ^{-1}) mod 998244353998244353.



For N = 2, the probability of alex winning the game is 1112\frac{11}{12}.



100% Solution Ratio

steinumEarliest, Sep '20

Deshi_TouristFastest, 0.4s

steinumLightest, 481 MB

Deshi_TouristShortest, 800B


Login to submit

Toph uses cookies. By continuing you agree to our Cookie Policy.