#exawizards2019e. [exawizards2019_e]Black or White
[exawizards2019_e]Black or White
Problem Statement
Today, Snuke will eat pieces of black chocolate and pieces of white chocolate for an afternoon snack.
He will repeat the following procedure until there is no piece left:
- Choose black or white with equal probability, and eat a piece of that color if it exists.
For each integer from to (inclusive), find the probability that the color of the -th piece to be eaten is black. It can be shown that these probabilities are rational, and we ask you to print them modulo , as described in Notes.
Notes
When you print a rational number, first write it as a fraction , where are integers and is not divisible by (under the constraints of the problem, such representation is always possible). Then, you need to print the only integer between and , inclusive, that satisfies .
Constraints
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
Output
Print the answers in lines. In the -th line, print the probability that the color of the -th piece to be eaten is black, modulo .
Sample Input 1
Sample Output 1
- There are three possible orders in which Snuke eats the pieces:
- white, black, black
- black, white, black
- black, black, white
- with probabilities , respectively. Thus, the probabilities of eating a black piece first, second and third are and , respectively.
Sample Input 2
Sample Output 2
- They are and , respectively.