Many thanks to Clive Fraser who created this problem for us, mentioning that it was inspired by a family country walk!
Ann, Bob and Carol are enjoying a walk along a country lane on a glorious summer day. They are walking side by side, with Ann on the left, Bob in the middle and Carol on the right. They pass through a number of pretty country villages where most of the houses have brightly painted doors and windows. The majority of the doors are painted either red or white. This gives Ann the idea of playing a game as they walk along the lane. Whenever they pass a red door the person in the middle will change places with the person on the left. Whenever they pass a white door the person in the middle will change places with the person on the right. In this way they are continually changing places as they move down the lane.
After walking past the first 9 houses Ann is in the middle, with Bob on the left and Carol on the right (B A C).
The friends have walked past 2 red doors and 7 white doors. The friends cannot remember the order of the
doors that they have passed but it is easy to show that there are 6 possible orders which would leave the
friends in their current position. These are given in the table below.
W R W R W W W W W
W R W W W R W W W
W R W W W W W R W
W W W R W R W W W
W W W R W W W R W
W W W W W R W R W
If we take the order W W W R W R W W W as a specific example, we can show in the following table, how the
friends change places as they walk past the doors. Remember that the friends start with Ann on the left and
Carol on the right (A B C).
Start A B C
W A C B
W A B C
W A C B
R C A B
W C B A
R B C A
W B A C
W B C A
W B A C
You will be given the final positions of Ann, Bob and Carol at the end of their walk. You will also be given
the number of red and white doors that they have passed. You are asked to determine the number of different
orders of these doors that would lead to the friends being in these final positions. You can assume that no two
doors are ever encountered simultaneously. As the number of possible orders can become very large, you must give
your answer modulo 1000000007 (10^9 +7). In all puzzles the friends have the same starting position (A B C).
Input/Output description: The first line of the input data will be a single integer N for the number of
puzzles. Each of the next N lines contain the data for one of the puzzles. Each line contains 5
space-separated items. The first 3 items give the final order of the friends at the end of their walk. Item 4
is the number of red doors and item 5 is the number of white doors. Determine the number of different orders
of these doors that would lead to the friends being in the given final positions. Give your answer modulo
1000000007 and give all answers separated by spaces as a single string.
Example:
input:
3
B A C 2 7
A C B 7 16
C A B 89 75
answer:
6 74052 539440465