Back to General discussions forum

This is a fairly straightforward problem so it should attract a reasonable number of solutions. Hopefully it is not too similar to any previous problems. The main motivation for suggesting it is to be able to follow it with an advanced version which requires a more sophisticated approach. The following is a draft problem description:

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.

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