### PROBLEM LINK:

**Author:** Dmytro Berezin

**Tester:** Prateek Gupta

**Editorialist:** Hussain Kara Fallah

### PROBLEM EXPLANATION

Chef has an array consisting of **N** elements. Chef may pick any **2 adjacent** elements which are both positive, decrement each of them by 1, and increment the next one (in front of them) by 1. (If those elements were the last two elements he appends 1 to the end of the array). Chef wants you to count the number of **different** arrays that he is able to reach via any sequence of moves. Since answer is large calculate it modulo **10 ^{9}+7**

### DIFFICULTY:

easy-medium

### PREREQUISITES:

Dynamic Programming

### EXPLANATION:

According to the given constraints, chef won’t be able to construct an array having more than **60** elements (this can be proved by paper or maybe be writing a greedy checker).

Observe that two different sequences of moves (without considering the order of the moves) will lead to different resulting arrays. That’s because there will be at least one element which was variated differently between the two sequences of operations (You can prove that if you apply operations in order from left to right).

This problem is a Dynamic Programming exercise, let’s define a function that solves this problem

**dp[pos][deltapos][deltanxt]**

which denotes the number of different arrays that could be obtained by performing operations on the subarray starting from the element having index * pos* assuming that this element was changed by

*and the next element to the right was changed by*

**deltapos***.*

**deltanxt****(1 ≤ pos ≤ 60)**

**(-50 ≤ deltapos,deltanxt ≤ 50)**

The base case of our function would be

**dp[61][0][0] = 1**

The recurrence formula of our function is kind of easy to figure out, we should try all different ways of changing the element at the index * pos*, and it’s clear that we have

**min(arr**different ways (That’s because all elements must be positive during any move and we are decrementing both of

_{pos}+deltapos , arr_{nxt}+deltanxt) + 1**arr**).

_{pos}, arr_{pos+1}For each number of operations **op** **(0 ≤ op ≤ min(arr _{pos}+deltapos , arr_{nxt}+deltanxt) + 1)**, performing any of them would lead us to a different solution from all the others.

**For each (0 ≤ op ≤ min(arr _{pos}+deltapos , arr_{nxt}+deltanxt) + 1)**

**dp[pos][deltapos][deltanxt] += dp[pos+1][deltanxt-op][op]**

Performing * op* would substract

*from the next element and add*

**op***to the element after the next and our current element won’t be affected in future operations, so we may discard it from the state.*

**op**### AUTHOR’S AND TESTER’S SOLUTIONS:

**AUTHOR’s solution**: Can be found here

**TESTER’s solution**: Can be found here

**EDITORIALIST’s solution**: Can be found here