We say an infinite sequence $a_{0}, a_{1}, a_2, \ldots$ is non-increasing if and only if for all $i\ge 0$, $a_i \ge a_{i+1}$.

There is an infinite right and down grid. The upper-left cell has coordinates $(0,0)$. Rows are numbered $0$ to infinity from top to bottom, columns are numbered from $0$ to infinity from left to right.

There is also a non-increasing infinite sequence $a_{0}, a_{1}, a_2, \ldots$. You are given $a_0$, $a_1$, $\ldots$, $a_n$; for all $i>n$, $a_i=0$. For every pair of $x$, $y$, the cell with coordinates $(x,y)$ (which is located at the intersection of $x$-th row and $y$-th column) is white if $y<a_x$ and black otherwise.

Initially there is one doll named Jina on $(0,0)$. You can do the following operation.

Select one doll on $(x,y)$. Remove it and place a doll on $(x,y+1)$ and place a doll on $(x+1,y)$.

Note that multiple dolls can be present at a cell at the same time; in one operation, you remove only one. Your goal is to make all white cells contain $0$ dolls.

What's the minimum number of operations needed to achieve the goal? Print the answer modulo $10^9+7$.


-----Input-----

The first line of input contains one integer $n$ ($1\le n\le 2\cdot 10^5$).

The second line of input contains $n+1$ integers $a_0,a_1,\ldots,a_n$ ($0\le a_i\le 2\cdot 10^5$).

It is guaranteed that the sequence $a$ is non-increasing.


-----Output-----

Print one integer — the answer to the problem, modulo $10^9+7$.


-----Examples-----

Input
2
2 2 0
Output
5
Input
10
12 11 8 8 6 6 6 5 3 2 1
Output
2596


-----Note-----

Consider the first example. In the given grid, cells $(0,0),(0,1),(1,0),(1,1)$ are white, and all other cells are black. Let us use triples to describe the grid: triple $(x,y,z)$ means that there are $z$ dolls placed on cell $(x,y)$. Initially the state of the grid is $(0,0,1)$.

One of the optimal sequence of operations is as follows:

Do the operation with $(0,0)$. Now the state of the grid is $(1,0,1),(0,1,1)$.

Do the operation with $(0,1)$. Now the state of the grid is $(1,0,1),(1,1,1),(0,2,1)$.

Do the operation with $(1,0)$. Now the state of the grid is $(1,1,2),(0,2,1),(2,0,1)$.

Do the operation with $(1,1)$. Now the state of the grid is $(1,1,1),(0,2,1),(2,0,1),(1,2,1),(2,1,1)$.

Do the operation with $(1,1)$. Now the state of the grid is $(0,2,1),(2,0,1),(1,2,2),(2,1,2)$.

Now all white cells contain $0$ dolls, so we have achieved the goal with $5$ operations.

Difficulty: HARD
Tags: Combinatorics

Mathematics

Starter code:

Solutions:
import sys

def solve():
	F = [None] * int(400000.0 + 4)
	Finv = [None] * len(F)
	F[0] = 1
	MOD = int(1000000000.0 + 7)
	for i in range(1, len(F)):
		F[i] = F[i - 1] * i % MOD
	Finv[-1] = pow(F[-1], MOD - 2, MOD)
	for i in range(len(F) - 1, 0, -1):
		Finv[i - 1] = Finv[i] * i % MOD
	inp = sys.stdin.readline
	n = int(inp())
	a = list(map(int, inp().split()))
	r = 0
	for i in range(n + 1):
		if a[i] > 0:
			r = (r + F[a[i] + i] * Finv[a[i] - 1] * Finv[i + 1]) % MOD
	print(r)

def main():
	solve()
main()


mod = 10 ** 9 + 7
m = 4 * 10 ** 5 + 1
f = [None] * m
f[0] = 1
for i in range(1, m):
	f[i] = f[i - 1] * i % mod
f_inv = [None] * m
f_inv[-1] = pow(f[-1], mod - 2, mod)
for i in reversed(range(1, m)):
	f_inv[i - 1] = f_inv[i] * i % mod
input()
print(sum((f[a + i] * f_inv[a - 1] * f_inv[i + 1] for (i, a) in enumerate(map(int, input().split())) if a > 0)) % mod)


MOD = 10 ** 9 + 7
ans = 0
fact = [1]
for i in range(1, 4 * 10 ** 5 + 5):
	fact.append(fact[-1] * i % MOD)

def c(m, n):
	return fact[m] * pow(fact[m - n] * fact[n], -1, MOD)
n = int(input())
for (i, a) in enumerate(map(int, input().split())):
	if a > 0:
		ans += c(a + i, i + 1) % MOD
		ans %= MOD
print(ans)


M = 1000000007
n = int(input())
arr = (*map(int, input().split()),)
N = max((arr[i] + i for i in range(n))) + 2
facts = [1]
for i in range(1, N + 1):
	facts.append(facts[-1] * i % M)
invnums = [0] * (N + 1)
invfacts = [0] * (N + 1)
invnums[0] = 1
invnums[1] = 1
invfacts[0] = 1
invfacts[1] = 1
for i in range(2, N + 1):
	invnums[i] = invnums[M % i] * (M - M // i) % M
	invfacts[i - 1] = invnums[i - 1] * invfacts[i - 2] % M
invfacts[N] = invnums[N] * invfacts[N - 1] % M

def comb(n, r):
	return facts[n] * invfacts[n - r] % M * invfacts[r] % M
ans = 0
for i in range(n + 1):
	if arr[i]:
		ans = (ans + comb(i + arr[i], i + 1)) % M
print(ans)


N = int(input())
x = list(map(int, input().split()))
ans = 0
MOD = 1000000007
for i in range(0, len(x)):
	x[i] += i
if x[0] == 0:
	ans = 0
else:
	tmp = x[0]
	ll = x[0]
	lr = x[0]
	r = 1
	for i in range(0, len(x)):
		while lr < x[i]:
			lr += 1
			tmp *= lr
			tmp %= MOD
		while lr > x[i]:
			if lr > 0:
				tmp *= pow(lr, -1, MOD)
				tmp %= MOD
			lr -= 1
		while ll > lr - i:
			ll -= 1
			tmp *= ll
		while ll < lr - i:
			if ll > 0:
				tmp *= pow(ll, -1, MOD)
				tmp %= MOD
			ll += 1
		while r <= i:
			r += 1
			tmp *= pow(r, -1, MOD)
			tmp %= MOD
		tmp = int(tmp)
		ans += tmp
		ans = int(ans)
		ans %= MOD
print(int(ans))


import gc
import math
from collections import Counter, deque, defaultdict
from sys import stdout
import time
from math import factorial, log, gcd
import sys
from decimal import Decimal
import threading
from heapq import *

def S():
	return sys.stdin.readline().split()

def I():
	return [int(i) for i in sys.stdin.readline().split()]

def II():
	return int(sys.stdin.readline())

def IS():
	return sys.stdin.readline().replace('\n', '')

def main():
	n = II()
	a = I()
	ans = 0
	for i in range(n + 1):
		el = a[i]
		if el > 0:
			d = fact[el + i] * pow(fact[i + 1], -1, mod) * pow(fact[el - 1], -1, mod)
			ans += d
		else:
			break
	print(ans % mod)
mod = 10 ** 9 + 7
fact = [1] * (4 * 10 ** 5 + 3)
for i in range(2, 4 * 10 ** 5 + 3):
	fact[i] = i * fact[i - 1] % mod
main()


M = 10 ** 9 + 7
fact = [1 for i in range(400007)]
for i in range(1, 400007):
	fact[i] = fact[i - 1] * i % M

def ncr(n, k):
	return fact[n] * pow(fact[n - k], -1, M) * pow(fact[k], -1, M) % M
N = int(input())
a = [int(i) for i in input().split()]
s = 0
for i in range(N + 1):
	if a[i] == 0:
		break
	s += ncr(a[i] + i, i + 1)
	s %= M
print(s)