All submissions for this problem are available.
kennyS has just finished his homework and wants to spend his time playing with marbles. Each marble has a beauty value bi assigned to it. He has kept the N beautiful marbles in straight line. Each marble also has some appealing factor ai. Shoxie, his friend, taught him a new game to play with. He gave kennyS two integers and K and L. According to rules, kennyS can either [WAY 1] select two marbles of same beauty and swap them if the sum of the appealing factors is less than or equal to K, or [WAY 2] he can choose two marbles of different beauties and swap them if the sum of the appealing factors is less than or equal to L. kennyS has to tell Shoxie how many distinct sequences of beauties of marbles he can get. Shoxie being considerate enough lets kennyS tell the output modulo 109+7. Help kennyS.
First line contains three integers N, K and L. The following N lines contain two integers bi and ai.
Output one integer which is the answer to the question.
Should contain all the constraints on the input data that you may have. Format it like:
- 1 ≤ N ≤ 250000
- 1 ≤ K,L ≤ 1000000000
- 1 ≤ bi ≤ N
- 1 ≤ ai ≤ 1000000000
Input: 5 7 3 3 2 4 3 2 1 4 4 5 5 Output: 2
Example case 1.
Sequence 1: 3 – 4 – 2 – 4 – 5 Sequence 2: 2 – 4 – 3 – 4 – 5 The second sequence can be obtained from the first one by swapping the first and third marble (WAY 2). Note that swapping the 2nd and the 4th marble would have made no new sequence.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, 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, kotlin, PERL6, TEXT, SCM chicken, CLOJ, COB, FS|
Fetching successful submissions