There are lamps located along a street at positions , each with a power level . The -th lamp lights up an area within the range when turned on. Initially, some lamps are turned on, and some are turned off. The initial state of the lamp is denoted by if the lamp is on; if the lamp is off. The positions of the lamps are sorted in increasing order, i.e., for all
For each lamp , you need to determine a value , which is the minimum total distance you must walk to achieve the following:
If you cannot reach position while ensuring all lamps except lamp are turned off, then .
The task is to compute the sum of for all , modulo .
Note: You can only walk in areas illuminated by the lamps.
The first line contains one integer (), the number of test cases.
Then, for each test case:
The total sum of across all test cases does not exceed .
For each test, print one line consisting of one integer, the answer.
Let be the total sum of across all test cases.
| Subtasks | Additional restrictions | Points | Required Subtasks |
|---|---|---|---|
| 0 | Sample | 0 | - |
| 1 | 2 | - | |
| 2 | |||
| 3 | |||
| 4 | |||
| 5 | 4 | 1 | |
| 6 | 8 | 0, 2 | |
| 7 | 12 | ||
| 8 | 14 | ||
| 9 | - | 25 | 0, 1, 2, 3, 4, 5, 6, 7, 8 |
Figure 1. Initial state of Lamps.
Now let's look at what happens when you start at the first lamp.
Figure 2. The starting lamp is turned on.
Figure 3. Move to lamp 2 and turn it on.
Figure 4. Go back to lamp 1 and turn it off.
Figure 5. Go to lamp 3 and turn off lamp 2.
| 9 |
| - |
| 12 |
| 1, 2 |
| 14 |
| 1, 2, 3 |
| 0, 1, 2, 3, 5, 6 |
| 0, 1, 2, 3, 4, 5, 6, 7 |