{"raw_statement":[{"iden":"problem statement","content":"There are $N$ buildings along AtCoder road. Initially, the $i$\\-th building from the left has $A_i$ stories.\nTakahashi, the president of ARC Wrecker, Inc., can do the following operation any number of times, possibly zero:\n\n*   Choose a positive integer $X$ that he likes and shoot a cannonball at that height, which decreases by $1$ the number of stories in each building with $X$ or more stories.\n\nFind the number of possible final sceneries of buildings, modulo ($10^{9} + 7$).\nWe consider two sceneries A and B different when the following holds:\n\n*   let $P_i$ be the number of stories of the $i$\\-th building from the left in scenery A;\n*   let $Q_i$ be the number of stories of the $i$\\-th building from the left in scenery B;\n*   we consider sceneries A and B different when $P_i \\neq Q_i$ for one or more indices $i$."},{"iden":"constraints","content":"*   $1 \\leq N \\leq 100000$\n*   $1 \\leq A_i \\leq 10^{9}$\n*   All values in input are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$\n$A_1$ $A_2$ $\\cdots$ $A_N$"},{"iden":"sample input 1","content":"2\n1 2"},{"iden":"sample output 1","content":"4\n\nThere are four possible combinations of heights of the buildings, as follows:\n\n*   (Building $1$, Building $2$) = $(0, 0)$\n*   (Building $1$, Building $2$) = $(0, 1)$\n*   (Building $1$, Building $2$) = $(1, 1)$\n*   (Building $1$, Building $2$) = $(1, 2)$"},{"iden":"sample input 2","content":"6\n5 3 4 1 5 2"},{"iden":"sample output 2","content":"32"},{"iden":"sample input 3","content":"7\n314 159 265 358 979 323 846"},{"iden":"sample output 3","content":"492018656\n\nThere are $20192492160000$ possible final sceneries. The correct output is that number modulo $10^{9} + 7$, which is $492018656$."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}