The is created by Clive Fraser aka CSFPython - many thanks!
A board game consists of a linear sequence of squares. Players throw a six-sided die to determine the number
of squares to move their playing piece at each turn. Moves are forwards only.
The first move takes a player onto the board. So a first move throw of 5 takes a player to square 5 on the
board. The game ends when a player reaches the final square on the board. If a player is close to the final
square and throws a number which would take them beyond this square, they ignore this throw and continue
throwing the die until they get a number which keeps them on the board; so that they are either on or before
the final square. When all players have completed the game, the sequence of die throws for any given player
(excluding those that were ignored) must therefore be a sequence of numbers which adds up to be the number
of squares on the board.
initial position, players (A, B) at start:
_A_B_ ___ ___ ___ ___ ___ ___ ___ ___ ___
start 1 2 3 4 5 6 7 8 9
move#1, A casts 5:
__B__ ___ ___ ___ ___ _A_ ___ ___ ___ ___
start 1 2 3 4 5 6 7 8 9
move#2, A casts 3:
__B__ ___ ___ ___ ___ ___ ___ ___ _A_ ___
start 1 2 3 4 5 6 7 8 9
further moves, A casts 4, 6, 2 (all ignored), then at last 1:
__B__ ___ ___ ___ ___ ___ ___ ___ ___ _1_
start 1 2 3 4 5 6 7 8 9
You see, it is like "Snakes and Ladders" ancient game or also similar to "Backgammon" or "Nards" - but in this task we do not care about order of players or any interaction/competition among them at all.
The problem is to find out how many possible sequences there are for a board of given size and a given
six-sided die. The die has a different number on each of its 6 faces. However, unlike a normal die,
the numbers are not 1, 2, 3, 4, 5 and 6. None of the numbers on the die will be larger than 30.
Even for a small board, the number of possible sequences of die throws is a very large number.
You should give the answer modulo 1000000007 (10^9 + 7).
Because of the fact that there is an advanced version of this problem, you are asked not to post a solution to the simpler problem which will also solve the advanced problem.
Input/Output description:
The first line of the input data will contain 6 space-separated integers.
These are the numbers on the 6 faces of the die.
The next line contains a single integer N.
N lines of data follow. Each of these contains a single integer which is the number of squares on the board.
You need to find the number of possible die throw sequences for this size of board with the given die.
Combine all N answers into a single string, separated by single spaces.
Remember that each answer should be given modulo 1000000007.
Example:
input:
1 11 18 22 23 28
6
100
1000
10000
100000
1000000
10000000
answer:
85578459 787831311 569622963 602449829 723608589 229835172