LittleElephantAndIntervalsDiv1

Problem Statement

Little Elephant from the Zoo of Lviv has some balls arranged in a row. Each ball can be painted in one of two possible colors: black or white. Initially all the balls are painted white.

You are given an int M, which represents the number of balls in the row. The balls are numbered from left to right, starting from 1. You are also given two int[]s L and R. To repaint balls, Little Elephant wants to use a robot. The robot will paint the balls in several consecutive stages. For each i, the i-th stage (1-based index) will look as follows: First, the robot will choose one of the two colors: white or black. Then, the robot will paint the balls with indices from L[i-1] to R[i-1], inclusive, using the chosen color. (Painting a ball covers all previous layers of paint.)

Return the number of different colorings Little Elephant can get after the last stage. (Two colorings are considered different if there exists some ball that is white in one coloring and black in the other one).

Definition

Class:: LittleElephantAndIntervalsDiv1
Method:: getNumber
Parameters:: int, int[], int[]
Returns:: long
Method signature:: long getNumber(int M, int[] L, int[] R)
(be sure your method is public)

Constraints

M will be between 1 and 1,000, inclusive.
L will contain between 1 and 50 elements, inclusive.
R will contain the same number of elements as L.
Each element of R will be between 1 and M, inclusive.
i-th element of L will be between 1 and R[i], inclusive.

Examples

```
4
```
```
{1, 2, 3}
```
```
{1, 2, 3}
```
```
Returns: 8
```
In the three stages the robot will choose the color for balls number 1, 2, and 3. The choices are independent of each other. The last, fourth ball will always remain white. Thus there are 2*2*2 = 8 different colorings.
```
3
```
```
{1, 1, 2}
```
```
{3, 1, 3}
```
```
Returns: 4
```
```
1000
```
```
{47}
```
```
{747}
```
```
Returns: 2
```

{5, 23, 4, 1, 15, 2, 22, 26, 13, 16, 28, 13, 27, 9, 18, 4, 10, 3, 4, 4, 3, 4, 1, 18, 18, 2, 38, 4, 10, 12, 3, 30, 11, 38, 2, 13, 1, 13, 18, 16, 13, 2, 14, 27, 13, 3, 26, 19, 5, 10}

{30, 41, 17, 1, 21, 6, 28, 30, 15, 19, 31, 28, 35, 27, 30, 13, 31, 5, 8, 25, 40, 10, 3, 26, 23, 9, 40, 8, 40, 23, 12, 37, 35, 39, 11, 34, 10, 21, 22, 21, 24, 5, 39, 27, 17, 16, 26, 35, 25, 36}

Returns: 256

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.