小华正在和她的小伙伴玩跳房子游戏。这是一个加强版的跳房子，每一行的格子数量可能超过 2 个。
这个游戏需要在地面上画了n排格子，其中第i排包含a[i]个格子。（保证两端的这两排仅有一个格子）
之后规定两端的这两个格子分别为起点和终点，小朋友从起点出发，每次可以跳到下一排或下两排的某个格子，直到抵达终点.
现在小华想知道从起点到终点共有多少种跳法，你能回答她的问题吗？答案对1000000007取模。
输入格式
第一行输入一个正整数n，其中（3 <= n <= 100000）。 第二行输入n个正整数，分别表示从起点到终点每排的格子数a[i]，以空格隔开。（1 <= a[i] <= 1000，保证起点和终点所在的排格子数为1）。
输出格式
输出一个正整数表示跳法的数量，答案对1000000007取模。