G. Qatada or Qashata Stick
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Qatada has always been determined to change his lifestyle. After years of skipping proper meals and relying on whatever he could find, he finally decided to take his health seriously and gain weight in a controlled and consistent way.

On the famous Street of Hungres, a place owned by Mr. Krabs and known for its endless line of restaurants and legendary food quality, there are $$$n$$$ restaurants placed in a straight line. Each restaurant serves food with a certain rating, representing how "effective" it is for Qatada's weight-gain plan.

Danial, who has been accompanying Qatada on this journey, hands him an array $$$a$$$ of length $$$n$$$ describing these restaurants.

If the value of $$$a_i \ne -1$$$, then it represents the fixed rating of the $$$i$$$-th restaurant. If $$$a_i = -1$$$, then the rating of that restaurant is unknown because Plankton has secretly tampered with the restaurant ratings while trying to steal the Krabby Patty formula, and Qatada is allowed to replace it with any integer value from $$$l$$$ to $$$r$$$ after carefully inspecting the menu.

However, Danial warns him that not every combination of choices will lead to a stable plan. After replacing all $$$-1$$$ values with valid integers, the resulting array must satisfy certain conditions.

First, no two adjacent restaurants are allowed to have the same rating. Formally, $$$ a_i \ne a_{i+1} \ \forall\, 1 \le i \lt n $$$

Second, Danial believes that a successful weight-gain plan must maintain a certain balance, so the total sum of all ratings in the final array must be odd, i.e., $$$ \sum_{i=1}^{n} a_i \equiv 1 \pmod{2}. $$$

Now Qatada wants to determine how many different valid arrays can be formed after replacing all $$$-1$$$ values such that both conditions are satisfied. Since the answer can be very large, output it modulo $$$10^9 + 7$$$.

Input

The first line contains three integers $$$n, l, r$$$ $$$(1 \le n \le 10^5, 1 \le l \le r \le 10^{18})$$$ — the number of restaurants on the Street of Hungres and the allowed range of ratings respectively.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$, where each $$$a_i$$$ is either $$$-1$$$ or satisfies $$$l \le a_i \le r$$$, describing the initial ratings of the restaurants. If $$$a_i = -1$$$, the rating of the $$$i$$$-th restaurant is unknown and must be chosen from the range $$$[l, r]$$$.

It is guaranteed that the first and last elements of the array are fixed, i.e., $$$a_1 \ne -1$$$ and $$$a_n \ne -1$$$.

Output

Print a single integer representing the number of valid ways to replace all $$$-1$$$ values under Danial conditions $$$\pmod{10^9 + 7}$$$.

Examples
Input
5 2 7
4 -1 4 2 5
Output
2
Input
6 1 4
3 -1 -1 4 -1 1
Output
7