Many thanks to Clive Fraser for creating this puzzle!
Anne and Bob have a pet rat called Roland. Roland is a particularly intelligent rat who enjoys
taking part in the numerous experiments devised by Anne and Bob to test his intellectual powers. The latest
experiment consists of a special cage built onto a model railway truck. The truck is free to move along a
straight track with buffers at each end. The track is marked out in a sequence of short equal-length sections.
The truck is moved by means of a stepper motor. A signal of 1 to the motor moves the truck forwards (by one
step) into the next section. A signal of 0 to the motor moves the truck backwards by one step into the
previous section. Inside the cage there is a small display screen. The electronics inside the truck will display
one of two images on the display screen. The images correspond to the two signals 0 and 1. Below the display
screen there are two switches which can easily be operated by Roland. The switches also have mini-display
screens on them. One of the switches always displays the same image as the one currently shown on the main
display screen. The other switch displays a third image which is not the same as either of the two images
corresponding to the signals 0 and 1. The third image remains constant.
At the start of the experiment the software controlling the truck is sent a sequence of 0/1 signals generated
at random. We will refer to this as the Signal Sequence. The software takes each signal from this sequence
in turn and displays the corresponding image on the screen and on the switch which does not show the third image.
After some time has elapsed, Roland will press one of the two switches. If Roland chooses the switch with the
image corresponding to the one on the main screen then the associated signal is sent to the stepper motor and
the truck moves forwards or backwards by one step. If Roland presses the switch with the third image on it the
current signal is discarded and the truck is not moved. After Roland has pressed one of the switches the next
signal in the Signal Sequence is used to reset the displays. The process continues until there are no more
signals remaining in the Signal Sequence. If the truck is ever at either end of the track, in contact with the
buffers, it clearly cannot move in a direction which would take it into the buffers. In this situation the
software automatically discards a 0/1 signal from the Signal Sequence if it would produce movement into the
buffers. Several signals may need to be discarded before a signal corresponding to movement away from the
buffers appears. At this point the usual process takes place; where Roland decides whether to accept or reject the
symbol by pressing one of the two switches.
Anne and Bob plan to use a variety of different images and a series of rewards to analyse Roland's behaviour as
the experiment progresses. However, they do not want things to be over-complicated initially and decide that it
makes sense to analyse the behaviour of the initial set-up first before adding anything else to it. The track is
of length M sections. These are numbered alongside the track from 0 to M-1. A move forwards moves the
truck to a section with a number one higher than that of the current section. The software in the truck records
the movements made by the truck in a Move Sequence. It uses the same two symbols, 1 for forwards and 0 for
backwards. Hence the Move Sequence simply consists of the signals from the Signal Sequence which were accepted
(rather than rejected) by Roland. Clearly signals which would move the truck into the buffers are rejected by
the software and also cannot be present in the Move Sequence.
Consider the following simple example. The track is of length M = 7 so has sections numbered from 0 to 6.
The truck is initially positioned at section 3. The Signal Sequence is 101110. The Move sequence is
initially empty. The following table shows the result of each of the 6 signals in the Signal Sequence in turn.
The Move Sequence is represented by MS and the position of the truck by P.
START P = 3 MS = ''
'1' Accepted by Roland P = 4 MS = '1'
'0' Rejected by Roland P = 4 MS = '1'
'1' Accepted by Roland P = 5 MS = '11'
'1' Accepted by Roland P = 6 MS = '111'
'1' Rejected by software P = 6 MS = '111'
'0' Accepted by Roland P = 5 MS = '1110'
We can see that Roland has pressed the accept switch on four occasions and the reject switch on one occasion.
When the truck was at position P = 6 it was up against the buffer at the end of the track. The next signal
from the Signal Sequence was 1. This would move the truck into the buffer so was rejected by the software and
not offered as a choice to Roland. The four accepted signals form the final Move Sequence 1110 which means
that the final position of the truck is at P = 5.
If we consider the initial Signal Sequence in isolation it would be useful to know how many different Move Sequences could be generated from it. The answer is 24. The possible Move Sequences are:
'', '0', '00', '01', '010', '011', '0110', '0111', '01110', '1', '10', '100', '101', '1010', '1011', '10110', '10111',
'101110', '11', '110', '111', '1110', '1111', '11110'
Notice that the first of these sequences is an empty string. This corresponds to a situation where Roland
rejects each of the signals in the Signal Sequence. Note that a Move Sequence like 01 could have been
generated by Roland accepting any of the latter three 1 signals from the Signal Sequence to generate the
forwards move. It is not important to know which of these was chosen and this information is clearly not
recorded in the Move Sequence. As we are concerned only with distinct Move Sequences we count 01 as a single
sequence. Of the 24 Move Sequences shown above, only 22 of them could have been created by Roland in the
previous example. The final two (1111, 11110) could not have been created because each of the sequences
requires a move forwards from position P = 6 which is at the end of the track. Of the 22 valid Move
Sequences 1 would move the truck to position 1, 3 move the truck to position 2, 5 move the truck to
position 3 (its original starting point), 6 move the truck to position 4, 5 move the truck to position
5 and 2 move the truck to position 6. Note that none of the Move Sequences would result in the truck
reaching position 0.
At the end of each experiment the truck will have reached some position P and the software will output the
Move Sequence which took it to that position. Ann and Bob are curious to know how many Move Sequences (based on
the same Signal Sequence and starting position) would have moved the truck to the same final position. This is
what you are asked to calculate.
Input and Answer
The first line of the problem will be a single integer N denoting the number of test cases.
Each of the following N lines will hold 3 integers followed by a string, all separated by single spaces.
The integers, in order, are the track length M, the start position of the truck S and the final position of
the truck P. The string is the Signal Sequence. It will consist only of the symbols 0 and 1 and will have
a length not greater than 94. For each test case you must find the number of different Move Sequences which
would move the truck from the given start position S to the final position P. Give these answers, separated
by spaces, as a single string.
Example:
input:
4
7 3 4 101110
40 26 21 0011011110001
25 18 22 100001101010000111
85 55 41 00001000001111000001010111010
answer:
6 4 72 193