Agenda de Oficinas
Um festival oferece n oficinas. A oficina i ocupa o intervalo semiaberto de tempo [si,ei) e fornece satisfação pi se frequentada. Uma pessoa pode participar de qualquer subconjunto de oficinas, desde que seus intervalos não se sobreponham; o final de uma pode coincidir com o início de outra. Oficinas com índices diferentes contam como escolhas diferentes, mesmo se seus horários e valores forem iguais.
Determine a satisfação máxima possível e quantos subconjuntos distintos atingem esse máximo, módulo 1000000007. O conjunto vazio é permitido.
Input
A primeira linha contém n. Cada uma das próximas n linhas contém si ei pi.
Restrições:
1 ≤ n ≤ 200000; 0 ≤ si < ei ≤ 10^9; 0 ≤ pi ≤ 10^9.
Output
Imprima maximo quantidade, sendo a quantidade tomada módulo 1000000007.
Samples
Sample 1
Input
3 1 3 4 3 5 5 1 5 9
Output
9 2
Há duas escolhas ótimas de valor 9: participar das duas primeiras oficinas ou apenas da terceira.