Sereja and Pairs
All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Sereja had an non-negative integer A in the range [0, 10100].
One day, he wrote N pairs of the form (X[i], floor(A / X[i]) ) on a piece of paper. Let us denote floor(A / X[i]) by D[i].
Sereja's little brother Sergey is very naughty, he changed the D values for some of the pairs. When confronted for his mischief by Sereja, he said that he did not touch more than K such pairs.
Now, given the modified values of N pairs of the form (X[i], D[i]), Sereja is wondering about number of possible original values of integer A. Please help Sereja so that little Sergey could avoid the upcoming beating by Sereja. As the answer could be large, please report it modulo 1000000007 (109+7).
First line of input contain an integer T — the number of test cases.T test cases follow.
First line of each test case contains integers N and K. Each of the next N lines contains a pair that Sereja wrote on the paper — X[i] and D[i] — as two space-separated integers.
OutputFor each test case, output a single line containing the answer - number of possible numbers A modulo (109+7).
- 1 ≤ T ≤ 5
- 0 ≤ K ≤ N ≤ 105
- 1 ≤ X[i] ≤ 109
- 0 ≤ D[i] ≤ 109
Input: 2 3 0 50 2 40 2 30 3 3 1 30 3 40 2 50 2 Output: 20 30
|Tags||cook64, easy-medium, greedy, implementation, maths, sereja, sorting|
|Time Limit:||3 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.