## Back to School '16: Textbooks

View as PDF 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 .

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
```

Report an issue

## 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.

:(