405204: GYM101845 A Apple Trees

In the beginning God created the heaven and the earth, the next five days God created the light, the water, the sky, the land, the trees and the living creatures, and on the sixth day he formed a man from the dust of the ground, called Adam. Afterwards, God took one of the man’s ribs and made a woman from the rib, called Eve. Adam and Eve lived in peace and harmony in the land, until God told them they should not take any apple from the only apple tree in Earth (at that moment, in year 0).

How they disobeyed God is a story from another day, now we are interested in how apple trees population increased over all those years. Apple trees are very interesting because their cycle of life is the following: first an apple fall into the ground and immediately a new apple tree blooms, from this moment we consider this as an apple tree, exactly ten years later the tree is full-grown and it starts to generate apples, from here every ten years the tree generates f(x) apples, where and x is the age of the tree, note that x will be always be a multiple of 10. Every apple generated from a tree will fall into the ground and generate a new tree, finally every apple tree dies exactly at the age of 45.

Now we want to know how many apple trees will be living on Earth after n years of the creation. At year 0 the apple tree created by God was not full-grown (this happened 10 years later).

The input consists of only one integer n (0 ≤ n ≤ 10¹⁵) - the number of years after the creation of the Earth including Adam, Eve and the first apple tree.

Print a single integer - the number of apple trees on Earth at the end of the n - th year after the creation of Earth, as this number can be very big print it modulo 10⁹ + 7

9

1

10

17

44

77328

45

77327

In the first case, at 9th year there was on Earth only the apple tree that God first created.

In second case we have that in the 10th year the first apple tree was full-grown and 16 apples that belonged to that tree made new 16 trees, therefore there were 17 trees.

In fourth case, we have that at year 45 the first apple tree died, so it doesn't count anymore.