Simple single-player board game, expected score distribution This is the first problem I've posted here; please post criticisms in comments.

Summary

A game board consists of a starting space, an ending space, and between them are N spaces, each with an instruction. You begin on the starting space with 0 points to your credit. Flip a coin or roll a die to choose the number 1 or 2. Move forward that many spaces. Now look at the instruction on the space you landed on. The possible instructions consist of "Do nothing", "Score x points", and "Move forward y spaces and obey the instruction there". x and y are positive. After obeying the instruction, go back to the coin flip. When you land on or pass the ending square, the game is over.

Given a description of a game board (number of squares, instruction on each space) your code should calculate the probability distribution of possible ending scores. It's irrelevant how many turns are taken before the end.

Input


An unambiguous representation (in whatever format you desire, though numbers should be human-readable) of the instruction on each space. Numbers should be human-readable.


Output


A list of pairs of each possible score and the probability of obtaining that score (either an exact fraction or a real number accurate to at least four decimal places). Can be returned or output. It's optional to include scores that have 0 probability of occurring.


Scoring the entries


They must be correct to be considered; wrong answers don't count.
Code size. If you golf it please also post an ungolfed version; if you use a golfing language please post a good explanation.


Examples

Easy


Input

3

1
F2
1

Output

0 0.5    // rolled a 2 on first turn, game over
1 0.25   // rolled a 1 then a 1
2 0.25   // rolled a 1 then a 2



Complex


Input

16

2
1
0
5
10
F3
5
15
1
0
3
F3
5
0
0
5

Output

7   0.0234375
8   0.0078125
9   0.01171875
10  0.03515625
11  0.01171875
12  0.048828125
13  0.015625
14  0.015625
15  0.0732421875
16  0.0322265625
17  0.06005859375
18  0.015625
19  0.01171875
20  0.087890625
21  0.046875
22  0.0654296875
23  0.009765625
24  0.0107421875
25  0.064453125
26  0.0380859375
27  0.0380859375
28  0.001953125
29  0.0029296875
30  0.044677734375
31  0.023681640625
32  0.0281982421875
33  0.00390625
34  0.0029296875
35  0.015869140625
36  0.017333984375
37  0.0177001953125
38  0.0078125
39  0.0087890625
40  0.013916015625
41  0.015625
42  0.0096435546875
43  0.00390625
44  0.009033203125
45  0.0155029296875
46  0.010009765625
47  0.00567626953125
49  0.003662109375
50  0.0067138671875
51  0.003662109375
52  0.00274658203125
Stax, 56 55 bytesCP437
üZÄ^3Γ╥£X╜T∩L╖á↨→╘Oïë╢Δ╥∙Eü╦5├jC╩XpN◘╘♥«╟╝☻y╞╘wé↔Ioÿ≈⌐─

Run and debug online!
Warning: Takes a long time (around 5 minutes in my box) to run the large example.
Credits to the almighty rubber duck for -1 byte.
Input is a list of numbers. Scoring x points is represented by -x, and Move y steps forward and follow the instruction there is represented by y. So for example the small test case will be represented as [-1,2,-1].
Outputs in rational number, the output for the large case is like this:
7 3/128
8 1/128
9 3/256
10 9/256
11 3/256
12 25/512
13 1/64
14 1/64
15 75/1024
16 33/1024
17 123/2048
18 1/64
19 3/256
20 45/512
21 3/64
22 67/1024
23 5/512
24 11/1024
25 33/512
26 39/1024
27 39/1024
28 1/512
29 3/1024
30 183/4096
31 97/4096
32 231/8192
33 1/256
34 3/1024
35 65/4096
36 71/4096
37 145/8192
38 1/128
39 9/1024
40 57/4096
41 1/64
42 79/8192
43 1/256
44 37/4096
45 127/8192
46 41/4096
47 93/16384
49 15/4096
50 55/8192
51 15/4096
52 45/16384

Alternative version
Calculates the probability recursively instead of enumerating every possibility. Much faster. Not really golfed.
00\sn+~]]01\]]+Yd;%{;%=zi^]?i]+ys@iXd{{dx2&lt;;x|i-v@1&lt;+!C_E2u*s;x@0|m-s\mm:f;i({i+|i=!Ci2+mys@{{B;x@0|m-+rm+F{o{h}/{hh0_{H+F\m]ys+YdFUUv\ys@:fo{h}/mhh0_{H+F\J
Try and debug online!
The two different algorithms give the same result.
Explanation
Uses the unpacked version to explain. The size of the game board is stored in register x. The current position on the board is stored in register y. There is an extra flag (boolean) denoted bFlip that is stored on the stack, used to indicate the type of last instruction.
The complete unpacked version is 66 bytes.
X|2{v:Bx)0Y1~s{^,*y+Ycx&gt;{d1~}{v;@c1&lt;c~{-}{y+Yd}?}?F,dmo|RmNx|2u*+J

I will explain it part by part.
X|2{v:Bx)0Y1~s{     F,dm
X|2                        `2^x`
   {v                  m    For `[0..2^x-1]` do the following
     :Bx)                   Binary representation of the current loop index
                            Padded with zeros to make the length `l`.
                            Each binary represents a sequence of coin flip outcomes
         0Y1~s              Initialize `y` and current score to `0`, and `bFlip` to true
              {     F       Play the game as indicated by the sequence of coin flip outcomes
                     ,d     Clean up: remove `bFlip` from the stack.

The block that plays the game:
{^,*y+Ycx&gt;{d1~}{v;@c1&lt;c~{-}{y+Yd}?}?F
{                                   F    The loop as stated above
 ^                                       Increment current flip result
                                         Map the original [0,1] to [1,2], denote this as `n`.
  ,*                                     If last instruction is of the type `Score k points` (`k` may be `0`)
    y+Y                                      Move forward `n` steps and save the new current position to register `y`.
       cx&gt;{   }{                  }?     If already moved past the end
           d1~                               Mark this instruction as `Score 0 points` (or `Do nothing`)
                                         Else
                v;@                          Get current instruction
                   c1&lt;c~                     Get the type of current instruction and remember it
                        { }{    }?           If the current instruction is `Score k points`
                         -                       Score `k` points
                                             Else
                            y+Yd                 Move forward as the instruction indicates

After executing this, we have a list with 2^x elements containing the scores of all possible coin flips, with equal probabilities. The rest of the program is just converting them to the output.
o|RmNx|2u*+J
o|R             Convert to a list of pairs of [element, count of appearance]
   m            Map the array elements with the rest of the program, output the results on separate lines
    Nx|2u*+     Divide the count of appearance by `2^x` to get probability
           J    Join the two elements with a space