Planning (difícil) P65632

Statement

L’enunciat d’aquest problema és semblant a l’anterior (Planning). Les úniques diferències es troben en el format de l’entrada, en que ara la $n$ pot estar entre 1 i 1000, i en que la solució esperada és més eficient.

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb les dues hores $x$ i $y$ , seguides del nombre $n$ d’activitats possibles, seguit dels $n$ temps que es triga a fer cada activitat. Suposeu que les hores estan entre 00:00:00 i 23:59:59, que el temps $t = y - x$ compleix $1 \le t \le 1000$ , $1 \le n \le 1000$ , que el temps de cada activitat no és més gran que $t$ , i que tant les hores com els temps segueixen estrictament el bonic format dels exemples.

Sortida

Per a cada cas, escriviu el nombre total de maneres d’organitzar el dia mòdul $10^8 + 7$ .

Pista

Una solució acceptable per a aquest problema té cost $\Theta(nt)$ .

Public test cases

Input

12:00:00  12:00:04
2  0m 2s  0m 3s

12:00:00  12:00:05
2  0m 2s  0m 3s

12:00:00  12:00:06
2  0m 2s  0m 3s

04:55:59  05:12:39
5  1m 1s  12m 15s  15m 0s  0m 1s  0m 1s

00:00:00  00:16:40
5  0m 1s  0m 1s  0m 1s  0m 1s  0m 1s

Output

Information

Author: Ivan Geffner
Language: Catalan
Official solutions: C++
User solutions: C++