You are given three integers n, l, and r.

An array arr of length n is considered a ZigZag array if:

• l $\le$ arr[i] $\le$ r for every index $0 \le i < n$.

• Adjacent elements strictly alternate between increasing and decreasing throughout the array. That is, one of the following conditions must hold:

  • arr[0] $<$ arr[1] $>$ arr[2] $<$ arr[3] $\dots$

  • arr[0] $>$ arr[1] $<$ arr[2] $>$ arr[3] $\dots$

Return the total number of valid ZigZag arrays. Since the answer may be large, return it modulo $10^9 + 7$.

Constraints:

• $3 \le$ n $\le 2000$

• $1 \le$ l $<$ r $\le 2000$

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.