Rezolvare PBinfo #4580

Cerința

Se dau N progresii aritmetice. Pentru fiecare se cunoaşte valoarea primului element şi raţia. Se mai dă o valoare X.
Determinaţi numărul de şiruri strict crescătoare care au următoarele proprietăţi: primul termen are valoarea 0, ultimul termen are valoarea X, oricare doi termeni consecutivi sunt termeni consecutivi în cel puțin una dintre progresiile date.

Date de intrare

Fişierul progresii.in conţine pe prima linie 2 numere naturale separate printr-un spaţiu N şi X, cu semnificaţia din enunţ. Pe următoarele N linii sunt câte 2 numere naturale separate prin câte un spaţiu. Cele două numere de pe o linie reprezintă, în ordinea aceasta, primul termen apoi raţia unei progresii. Primul termen este un număr natural, iar raţia un număr natural nenul.

Date de ieșire

Pe prima linie a fişierului progresii.out se vor afla două numere naturale separate printr-un spaţiu reprezentând numărul de şiruri ce se pot forma respectând proprietăţile enunţate, precum şi lungimea maximă a unui astfel de şir. Primul numar va fi afisat modulo 2011.

Restricții și precizări

• 1 <= N, X <= 50000
• Pentru fiecare progresie, primul termen şi raţia sunt <= 50000;
• Raţiile tuturor progresiilor sunt numere distincte două câte două.

Exemplu:

progresii.in

2 6
0 2
4 1

progresii.out

2 5

Explicație

Sunt două şiruri ce se pot forma: 0 2 4 5 6 şi 0 2 4 6.