409864: GYM103811 H How to Get Rice

Once upon a time in India, there was a king who was a big fan in chess and had the habit of challenging wise visitors to a game of chess. One day, a sage visits the country and was challenged by the king. The sage gladly accepted. The king was so confident in himself that he offered any reward the sage asks for. The sage modestly asked just for a few grains of rice in the following manner: on the $$$8 \times 8$$$ chessboard, the king was to put a single grain of rice on the first chess square, then two grains on the second square, four grains on the third and so on, doubling each time while placing on every consequent square. The king accepted the sage's request.

The sage won the chess game, and it is time for the king to reward the sage. He ordered his servants to bring a bag of rice to the chessboard, and started placing rice grains according to the arrangement. The king quickly realised that he was unable to fulfill his promise, because by the 20th square there would be $$$1,048,575$$$ grains of rice placed on the chessboard, and when all 64 squares were filled, the king would have to put a total of $$$18,446,744,073,709,551,615$$$ on the chessboard.

From this point onwards versions of this story start to differ. Some say the king was furious and had the sage killed for tricking him; some have a happy ending and the sage became the wealthiest person in the world, with the king paying the debt in instalments. Here we modify the game: instead of placing rice grains on the chessboard, we place them in a bowl for reasons of hygiene; and instead of using a $$$8 \times 8$$$ chessboard, we use a customized $$$1 \times N$$$ one.

The operations are also modified. The game starts by placing a piece of chess on the leftmost Cell 1, and 1 grain of rice in the bowl, as well as a multiplier $$$K = 1$$$. Each time you are allowed to perform one of two operations:

1. Move 1 cell to the right, add 1 grain of rice to the bowl, and add 1 to the multiplier $$$K$$$.
2. Move $$$K$$$ cells to the right, and multiply the amount of rice in the bowl by $$$K$$$. The multiplier remains unchanged.

Your reward will be the amount of rice you have in the bowl once the piece of chess reaches Cell $$$N$$$. Obviously you cannot move that chess beyond Cell $$$N$$$ and out of the chessboard. What is the maximum amount of rice you can get? Since the actual amount can be astronomical as we saw in the story, output your answer modulo $$$1,000,000,007$$$.

A single integer $$$N$$$ – the length of the board. ($$$1 \le N \le 10^{9}$$$)

Output a single integer $$$R$$$, the maximum amount of rice you can get, modulo $$$1,000,000,007$$$.

5

5

6

9

In Sample 1,

• Start at Cell 1, $$$R = 1, K = 1$$$
• Move to Cell 2, $$$R = 2, K = 2$$$
• Move to Cell 4, $$$R = 4, K = 2$$$
• Move to Cell 5, $$$R = 5, K = 3$$$

In Sample 2,

• Start at Cell 1, $$$R = 1, K = 1$$$
• Move to Cell 2, $$$R = 2, K = 2$$$
• Move to Cell 3, $$$R = 3, K = 3$$$
• Move to Cell 6, $$$R = 9, K = 3$$$