Statistics

Stone solitaire is a single-player game played on a specially-crafted game board using some mutually indistinguishable stones.

The game board consists of a sequence of pits, sequentially numbered using non-negative integers. Each pit may contain arbitrarily many stones.

The goal of the game is to move all stones into pit number zero.

In a move the player performs the following steps:

1. Selects a non-empty pit with a positive label.
2. Notes the label x of the selected pit.
3. Picks up all the stones from the selected pit.
4. Redistributes the stones into pits with the next lower numbers (x-1, x-2, ...), placing exactly one stone into each pit.

If the player runs out of available pits while still trying to redistribute some stones, the player immediately loses the game.

In a turn the player starts by making a move. The move can have four possible outcomes:

1. Obviously, if the player performed a move that caused them to lose the game, the whole game is now over and the player lost.
2. If after the move all stones are now in pit number zero, the player won the game.
3. If during the move the last stone was placed into a pit with a positive label, the turn is over.
4. If during the move the last stone was placed exactly into pit number zero, the player gets to continue the turn by making another move.

The last rule applies to all moves made during the turn. Hence, if a player can find a suitable sequence of moves, their turn may consist of arbitrarily many moves.

For example, suppose the player starts a turn in a position where there are fifteen stones: one in pit 1, one in pit 2, three in pit 3, and ten in pit 7.

In the first move the player can choose any of the pits 1, 2, 3, and 7. These choices will have the following effect:

• If the player chooses pit 1, they pick up the one stone from there and place it into pit 0. The move ends, and as the last stone was placed into pit 0, they get another move within the same turn.
• If the player chooses pit 2, they pick up the one stone from there and place it into pit 1. The move ends and then the turn ends.
• If the player chooses pit 3, they pick up the three stones from there. Then, they place one stone into pit 2, one into pit 1, and the final one into pit 0. In this case the player also gets to make another move this turn.
• If the player chooses pit 7, they pick up the ten stones from there. Then, they place seven of those stones into pits 6 through 0. The player now needs to place three more stones but there are no more pits left, so the player loses the game.

A position is winning if pit number zero is empty and there is a way to win the game in a single turn.

The hash of a position in which pit x contains C[x] stones, for all x, is the sum of C[x]*10^x over all x.

Given N, find all positions that are winning and consist of exactly N stones. Return the sum of their hashes, modulo 10^9 + 7.