Se dau N progresii aritmetice. Pentru fiecare se cunoaşte valoarea primului element şi raţia. Se mai dă o valoare X.
Cerinţă
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 aceeaşi progresii.
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. Raţiile tuturor progresiilor sunt numere distincte două câte două.
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
1 <= N, X <= 50000
Pentru fiecare progresie, primul termen şi raţia sunt <= 50000;
Pentru determinarea doar a primei valori se acordă 50% din punctaj.
Exemplu
progresii.in
progresii.out
Explicaţie
2 6
0 2
4 1
2 5
Sunt două şiruri ce se pot forma: 0 2 4 5 6 şi 0 2 4 6.