## Back to School '16: Textbooks

View as PDFbobhob314 has applied some super sticky substance to his textbooks. This mysterious substance is so sticky that it prevents textbooks from falling off ledges in a tetris-like manner. The ^{th} textbook is placed starting at and is units long and wide. The textbooks are given in the order in which they are placed.

The sun is shining directly above and bobhob314 wants to protect more books from the sun. Find the total area unoccupied by a textbook in the shade (has at least one part of a textbook above). Print this modulo .

#### Input Specification

The first line contains a single integer .

The next lines contain space separated integers, , and .

**Note:** fast input may be required.

#### Constraints

##### Subtask 1 [10%]

##### Subtask 2 [30%]

##### Subtask 3 [60%]

#### Output Specification

Output a single integer, the number of empty spaces under at least one textbook modulo .

#### Sample Input 1

```
3
1 3 1
3 3 1
5 3 1
```

#### Sample Output 1

```
6
```

#### Sample Input 2

```
5
1 2 1
3 1 1
3 4 1
6 3 2
5 2 1
```

#### Sample Output 2

```
9
```

#### Explanation for Sample Output 2

The textbooks are represented with a digit . A period represents a unit in the shade.

```
55
.444
.444
3333..
112.....
```

#### Sample Input 3

```
4
5 1 2
3 1 2
5 1 1
3 3 1
```

#### Sample Output 3

```
4
```

#### Explanation for Sample Output 3

```
444
..3
2.1
2.1
```

## Comments

If I'm not mistaken, test case 9 in subtask 1 has s>100 000 or l>100 000.

The test cases have been fixed

bobhob314 and his super sticky substance ( ͡° ͜ʖ ͡°)---->Suspicious.

:(