ARC Wrecker

AtCoder

IDarc117_b

Time2000ms

Memory256MB

Difficulty—

There are $N$ buildings along AtCoder road. Initially, the $i$\-th building from the left has $A_i$ stories. Takahashi, the president of ARC Wrecker, Inc., can do the following operation any number of times, possibly zero: * 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. Find the number of possible final sceneries of buildings, modulo ($10^{9} + 7$). We consider two sceneries A and B different when the following holds: * let $P_i$ be the number of stories of the $i$\-th building from the left in scenery A; * let $Q_i$ be the number of stories of the $i$\-th building from the left in scenery B; * we consider sceneries A and B different when $P_i \neq Q_i$ for one or more indices $i$. ## Constraints * $1 \leq N \leq 100000$ * $1 \leq A_i \leq 10^{9}$ * All values in input are integers. ## Input Input is given from Standard Input in the following format: $N$ $A_1$ $A_2$ $\cdots$ $A_N$ [samples]

Samples

Input #1

2
1 2

Output #1

4

There are four possible combinations of heights of the buildings, as follows:

*   (Building $1$, Building $2$) = $(0, 0)$
*   (Building $1$, Building $2$) = $(0, 1)$
*   (Building $1$, Building $2$) = $(1, 1)$
*   (Building $1$, Building $2$) = $(1, 2)$

Input #2

6
5 3 4 1 5 2

Output #2

Input #3

7
314 159 265 358 979 323 846

Output #3

492018656

There are $20192492160000$ possible final sceneries. The correct output is that number modulo $10^{9} + 7$, which is $492018656$.

API Response (JSON)

{
  "problem": {
    "name": "ARC Wrecker",
    "description": {
      "content": "There are $N$ buildings along AtCoder road. Initially, the $i$\\-th building from the left has $A_i$ stories. Takahashi, the president of ARC Wrecker, Inc., can do the following operation any number of",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "arc117_b"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "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...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments