## NOI '19 P5 - Landlords

View as PDF

Points: 25 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Kevin is playing cards and now he needs to shuffle cards times. Now let's describe the rule of the shuffle.

For the shuffle:

1. Kevin will take out cards from the top and make it a new pile. Now there are two piles of cards. One is the original top cards and the other is the rest cards. The relative order in these two piles remains unchanged. Note that when is or , there is one pile which has no card at all.

2. Now let's merge those two piles of cards into a new pile. Suppose the first pile has cards and the second piles has cards. With probability , we select the bottom card of the first pile and put the selected card to the top of the new pile. Then, with probability , we select the bottom card of the second pile and then put the selected card to the top of the new pile.

3. Repeat 2 until both piles are empty.

Now we have questions for you. You have to tell us after times of shuffles, what's the expected score of some specific positions' card. Note that for card , let's denote its score as . In this problem, equals to either or .

#### Input Specification

The first line contains three integers . When , . When , .

The following line contains integers .

The following line contains an integer .

In the following lines, each line contains an integer , indicating that Kevin wants to know the expected score of the position from top.

#### Constraints

For all test cases, .

11None
2
32
4All are equal
51None
6
7
82
9
10

#### Output Specification

For each query, output a single integer on a single line as the answer. If the answer is , please print where .

#### Sample Input 1

4 1 1
3
1
1

#### Sample Output 1

249561090