StickerMix | Practice Problems

StickerMix

★★★★★

2 votes

Number Theory, Algorithms, Math, Modulus Arithmetic

Details

Submissions

Discussion

Editorial

Problem

Imagine you have $N$ boxes labeled with unique stickers indicating what's inside. Now, You decide to be mischievous and randomly shuffle the stickers on these boxes. The challenge is to figure out the probability of exactly $i$ boxes ending up with the correct stickers modulo $1000000007$ after this playful (random) shuffle for each $i$ from $0$ to $N$ .

Note: It can be proved that the sought probability is always a rational number. Additionally, the constraints of this problem guarantee that if the sought probability is represented as an irreducible fraction $A/B$ , then $B$ is not divisible by $1000000007$ . Here, there is a unique integer $C$ such that $B×C≡A$ (mod $1000000007$ ). Report this $C \ (0 \leq C \lt 10^9 + 7)$ for every probability value.

Input format

The first line contains a single integer $T$ , which denotes the number of test cases.
For each test case:
- A line contains a single integer $N$ denoting the number of boxes.

Output format

For each test case, print $N+1$ integers in a new line, where the $i^{th}$ integer is the probability of exactly $(i-1)$ boxes ending up with the correct stickers modulo $1000000007$ after the playful (random) shuffle.

Constraints

$1 \leq T \leq 10^4 \\ 1 \leq N \leq 10^6 \\ \text{The sum of all values of N over all test cases doesn't exceed } 10^6$

Time Limit: 1

Memory Limit: 256

Source Limit:

Explanation

For test case $1$ :

N = 4

In a scenario with N=4, there are four distinct boxes, each with its unique sticker. The task is to determine the probability under modulo $1000000007$ , of exactly $i$ boxes ending up with the correct stickers after the playful (random) shuffle for each $i$ from $0$ to $N$ . The total number of such random arrangements of stickers is $24$ . The probabilities are calculated as follows:

The Probability of no box having the correct sticker: $9/24 ≡ 375000003$ (mod $1000000007$ ).
The probability of exactly one box having the correct sticker: $8/24 ≡ 333333336$ (mod $1000000007$ ).
The probability of exactly two boxes having the correct stickers: $6/24 ≡ 250000002$ (mod $1000000007$ ).
The probability of exactly three boxes having the correct stickers: $0/24 ≡ 0$ (mod $1000000007$ ).
The probability of all four boxes having the correct stickers: $1/24 ≡ 41666667$ (mod $1000000007$ ).