Sakuyalove finds a triangle pyramid which contains many nodes with its own A/virus value. Out of curiosity, Sakuyalove is trying to calculate the summation of A/virus value in all of the nodes in the pyramid. 

It is noticed that, the triangle pyramid consists of n layers, and the i^th layer consists of i nodes. At the top of the triangle pyramid, which is known as the single node in the 1^st layer, there is 1 A/virus value in this node. 

As we know, A/virus is contagious, since there are more and more A-soul fans on the planet. During the process of propagation from the top layer to the bottom layer, each node will propagate its A/virus value to its bottom node and its bottom-right node, which means the final A/virus value of certain node is the summation A/virus value of its top node (if it exists) and its top-left node (if it exists). Sakuyalove wants to calculate the summation of A/virus value in all of the nodes in this triangle pyramid to speculate whether the planet can still be saved. Please help her.

Note: Since the summation of A/virus value may be very large, you just need to output the answer modulo 10⁹+7.