Problem:
 Score : 1000 points    Problem Statement Snuke arranged N colorful balls in a row.
The i -th ball from the left has color c_i and weight w_i .  He can rearrange the balls by performing the following two operations any number of times, in any order:   Operation 1 : Select two balls with the same color. If the total weight of these balls is at most X , swap the positions of these balls.  Operation 2 : Select two balls with different colors. If the total weight of these balls is at most Y , swap the positions of these balls.   How many different sequences of colors of balls can be obtained? Find the count modulo 10^9 + 7 .      Constraints  1 ≤ N ≤ 2 × 10^5  1 ≤ X, Y ≤ 10^9  1 ≤ c_i ≤ N  1 ≤ w_i ≤ 10^9  X, Y, c_i, w_i are all integers.         Input Input is given from Standard Input in the following format:  N  X  Y  c_1  w_1  :  c_N  w_N       Output Print the answer.        Sample Input 1 4 7 3
3 2
4 3
2 1
4 4      Sample Output 1 2   The sequence of colors (2,4,3,4) can be obtained by swapping the positions of the first and third balls by operation 2 .  It is also possible to swap the positions of the second and fourth balls by operation 1 , but it does not affect the sequence of colors.        Sample Input 2 1 1 1
1 1      Sample Output 2 1       Sample Input 3 21 77 68
16 73
16 99
19 66
2 87
2 16
7 17
10 36
10 68
2 38
10 74
13 55
21 21
3 7
12 41
13 88
18 6
2 12
13 87
1 9
2 27
13 15      Sample Output 3 129729600

Solution (Python):
class UnionFindVerSize():
    def __init__(self, N):
        self._parent = [n for n in range(0, N)]
        self._size = [1] * N

    def find_root(self, x):
        if self._parent[x] == x: return x
        self._parent[x] = self.find_root(self._parent[x])
        return self._parent[x]

    def unite(self, x, y):
        gx = self.find_root(x)
        gy = self.find_root(y)
        if gx == gy: return

        if self._size[gx] < self._size[gy]:
            self._parent[gx] = gy
            self._size[gy] += self._size[gx]
        else:
            self._parent[gy] = gx
            self._size[gx] += self._size[gy]

    def get_size(self, x):
        return self._size[self.find_root(x)]

    def is_same_group(self, x, y):
        return self.find_root(x) == self.find_root(y)

    def calc_group_num(self):
        N = len(self._parent)
        ans = 0
        for i in range(N):
            if self.find_root(i) == i:
                ans += 1
        return ans

mod = 10**9+7 
N = 2*10**5
g1 = [1, 1] 
g2 = [1, 1] 
inverse = [0, 1] 

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

import sys,bisect

input=sys.stdin.buffer.readline

N,X,Y=map(int,input().split())
cball=[[] for i in range(N)]
ball=[]
color=[-1]*N
for i in range(N):
    c,w=map(int,input().split())
    ball.append((w,c-1,i))
    cball[c-1].append((w,i))
    color[i]=c-1

for i in range(N):
    cball[i].sort()
ball.sort()

if N==1:
    print(1)
    exit()

cmin=[10**20 for i in range(N)]
for i in range(N):
    if cball[i]:
        cmin[i]=min(cball[i][j][0] for j in range(len(cball[i])))

_cmine1=[cmin[i] for i in range(N)]
_cmine2=[cmin[i] for i in range(N)]
for i in range(1,N):
    _cmine1[i]=min(_cmine1[i],_cmine1[i-1])
for i in range(N-2,-1,-1):
    _cmine2[i]=min(_cmine2[i],_cmine2[i+1])
cmine=[0]*N
cmine[0]=_cmine2[1]
cmine[-1]=_cmine1[N-2]
for i in range(1,N-1):
    cmine[i]=min(_cmine1[i-1],_cmine2[i+1])

M=min(ball)
special=-1
for i in range(N):
    if cmine[i]!=M[0]:
        special=i

uf=UnionFindVerSize(N)
for i in range(N):
    if i!=special:
        for j in range(len(cball[i])):
            if M[0]+cball[i][j][0]<=Y:
                uf.unite(cball[i][j][1],M[2])
            if j!=0 and cball[i][j][0]+cball[i][0][0]<=X:
                uf.unite(cball[i][j][1],cball[i][0][1])
    else:
        for j in range(len(cball[special])):
            if cmine[special]+cball[special][j][0]<=Y:
                uf.unite(cball[special][j][1],M[2])
            if M[0]+cball[special][j][0]<=X:
                uf.unite(cball[special][j][1],M[2])

connect={}
for i in range(N):
    root=uf.find_root(i)
    if root not in connect:
        connect[root]=[]
    connect[root].append(i)

ans=1
for root in connect:
    cc={}
    for i in connect[root]:
        if color[i] not in cc:
            cc[color[i]]=0
        cc[color[i]]+=1
    size=len(connect[root])
    for C in cc:
        ans*=g2[cc[C]]
        ans%=mod
    ans*=g1[size]
    ans%=mod

print(ans)

Solution (Python):
class Combination:
    def __init__(self, n_max, mod=10**9+7):
        
        self.mod = mod
        f = 1
        self.fac = fac = [f]
        for i in range(1, n_max+1):
            f = f * i % mod
            fac.append(f)
        f = pow(f, mod-2, mod)
        self.facinv = facinv = [f]
        for i in range(n_max, 0, -1):
            f = f * i % mod
            facinv.append(f)
        facinv.reverse()

import sys
N, X, Y = map(int, input().split())
CW = list(map(int, sys.stdin.read().split()))
C, W = CW[::2], CW[1::2]
mod = 10**9+7
comb = Combination(N+1)

Color_min = [10**10] * (N+1)
Color_argmin = [-1] * (N+1)
Color_2nd_min = [10**10] * (N+1)
all_min = 10**10
all_second_min = 10**10
all_min_color = -1
for i, (c, w) in enumerate(zip(C, W)):
    if Color_2nd_min[c] > w:
        Color_2nd_min[c] = w
        if Color_min[c] > w:
            Color_min[c], Color_2nd_min[c] = Color_2nd_min[c], Color_min[c]
            Color_argmin[c] = i
for c, w in enumerate(Color_min):
    if all_second_min > w:
        all_second_min = w
        if all_min > w:
            all_min, all_second_min = all_second_min, all_min
            all_min_color = c
    
In_cnt = [0] * (N+1)
Out_flag= [0] * (N+1)
for i, (c, w) in enumerate(zip(C, W)):
    if (i != Color_argmin[c] and Color_min[c] + w <= X) \
     or (Color_2nd_min[c] + w <= X) \
     or (c != all_min_color and all_min + w <= Y) \
     or (all_second_min + w <= Y):
        In_cnt[c] += 1
    if all_min + w <= Y:
        Out_flag[c] = 1
sum_in_out = 0
ans = 1
for c, f in zip(In_cnt, Out_flag):
    if f:
        sum_in_out += c
        ans = ans * comb.facinv[c] % mod
ans = ans * comb.fac[sum_in_out] % mod


print(ans)

Solution (Python):
import sys
readline = sys.stdin.readline

class Segtree:
    def __init__(self, A, intv, initialize = True, segf = max):
        self.N = len(A)
        self.N0 = 2**(self.N-1).bit_length()
        self.intv = intv
        self.segf = segf
        if initialize:
            self.data = [intv]*self.N0 + A + [intv]*(self.N0 - self.N)
            for i in range(self.N0-1, 0, -1):
                self.data[i] = self.segf(self.data[2*i], self.data[2*i+1]) 
        else:
            self.data = [intv]*(2*self.N0)
        
    def update(self, k, x):
        k += self.N0
        self.data[k] = x
        while k > 0 :
            k = k >> 1
            self.data[k] = self.segf(self.data[2*k], self.data[2*k+1])
    
    def query(self, l, r):
        L, R = l+self.N0, r+self.N0
        s = self.intv
        while L < R:
            if R & 1:
                R -= 1
                s = self.segf(s, self.data[R])
            if L & 1:
                s = self.segf(s, self.data[L])
                L += 1
            L >>= 1
            R >>= 1
        return s
    
    def binsearch(self, l, r, check, reverse = False):
        L, R = l+self.N0, r+self.N0
        SL, SR = [], []
        while L < R:
            if R & 1:
                R -= 1
                SR.append(R)
            if L & 1:
                SL.append(L)
                L += 1
            L >>= 1
            R >>= 1
        
        if reverse:
            for idx in (SR + SL[::-1]):
                if check(self.data[idx]):
                    break
            else:
                return -1
            while idx < self.N0:
                if check(self.data[2*idx+1]):
                    idx = 2*idx + 1
                else:
                    idx = 2*idx
            return idx - self.N0
        else:
            pre = self.data[l+self.N0]
            for idx in (SL + SR[::-1]):
                if not check(self.segf(pre, self.data[idx])):
                    pre = self.segf(pre, self.data[idx])
                else:
                    break
            else:
                return -1
            while idx < self.N0:
                if check(self.segf(pre, self.data[2*idx])):
                    idx = 2*idx
                else:
                    pre = self.segf(pre, self.data[2*idx])
                    idx = 2*idx + 1
            return idx - self.N0

MOD = 10**9+7
def frac(limit):
    frac = [1]*limit
    for i in range(2,limit):
        frac[i] = i * frac[i-1]%MOD
    fraci = [None]*limit
    fraci[-1] = pow(frac[-1], MOD -2, MOD)
    for i in range(-2, -limit-1, -1):
        fraci[i] = fraci[i+1] * (limit + i + 1) % MOD
    return frac, fraci
frac, fraci = frac(1341398)
INF = 10**9+7
N, X, Y = map(int, readline().split())

CW = [tuple(map(int, readline().split())) for _ in range(N)]
Cw = [[] for _ in range(N)]
Cwidx = [[] for _ in range(N)]
used = set()

for i in range(N):
    c, w = CW[i]
    c -= 1
    Cw[c].append(w)
    used.add(c)
    Cwidx[c].append(i)

if len(used) == 1:
    print(1)
else:
    C, W = map(list, zip(*CW))
    minw = [INF]*N
    size = [0]*N
    T = Segtree(W, INF, initialize = True, segf = min)
    N0 = T.N0
    for col in range(N):
        if Cw[col]:
            for idx in Cwidx[col]:
                T.update(idx, INF)
            
            minv = T.query(0, N0)
            L = Cw[col]
            L.sort()
            LL = len(L)
            
            ok = -1
            ng = LL
            limit = max(X-L[0], Y-minv)
            while abs(ok-ng) > 1:
                med = (ok+ng)//2
                if L[med] <= limit:
                    ok = med
                else:
                    ng = med
            size[col] = ok+1
            minw[col] = L[0]
            for idx in Cwidx[col]:
                T.update(idx, W[idx])
    
    mw = min(W)
    minidxcol = C[W.index(mw)]-1
    candi = []
    for col in range(N):
        if mw+minw[col] <= Y or col == minidxcol:
            candi.append(size[col])
    ans = frac[sum(candi)]
    for c in candi:
        ans = ans*fraci[c]%MOD
    print(ans)

Solution (Python):
from collections import defaultdict

mod = 10**9+7
rng = 200100
fctr = [1]
finv = [1]
for i in range(1,rng):
  fctr.append(fctr[-1]*i%mod)
for i in range(1,rng):
  finv.append(pow(fctr[i],mod-2,mod))
def cmb(n,k):
  if n<0 or k<0:
    return 0
  else:
    return fctr[n]*finv[n-k]*finv[k]%mod

import sys
input = sys.stdin.readline
n,X,Y = map(int,input().split())
cw = [list(map(int,input().split())) for i in range(n)]
cw.sort()
mnls = []
graph = [[] for i in range(n)]
notmn = set()
for i in range(n):
  if i == 0 or cw[i-1][0] != cw[i][0]:
    mnls.append((i,cw[i][0],cw[i][1]))
  else:
    if cw[i][1]+mnls[-1][2] <= X:
      graph[i].append(mnls[-1][0])
      graph[mnls[-1][0]].append(i)
    else:
      notmn.add(i)
mnls.sort(key = lambda x:x[2])
for i,x in enumerate(mnls):
  if i == 0:
    continue
  if x[2]+mnls[0][2] <= Y:
    graph[x[0]].append(mnls[0][0])
    graph[mnls[0][0]].append(x[0])
for i in notmn:
  if mnls[0][1] != cw[i][0]:
    if mnls[0][2]+cw[i][1] <= Y:
      graph[i].append(mnls[0][0])
      graph[mnls[0][0]].append(i)
  else:
    if len(mnls) >= 2 and mnls[1][2]+cw[i][1] <= Y:
      graph[i].append(mnls[1][0])
      graph[mnls[1][0]].append(i)
vis = [0 for i in range(n)]
ans = 1
for i in range(n):
  if vis[i]:
    continue
  vis[i] = 1
  stack = [i]
  color = defaultdict(int)
  while stack:
    x = stack.pop()
    color[cw[x][0]] += 1
    for y in graph[x]:
      if vis[y] == 0:
        vis[y] = 1
        stack.append(y)
  sm = sum(color.values())
  for v in color.values():
    ans = ans*cmb(sm,v)%mod
    sm -= v
print(ans)

Solution (Python):

import sys;sys.setrecursionlimit(10**9)
class UnionFind:
  def __init__(self,n):
    self.n=[-1]*n
    self.r=[0]*n
    self.siz=n
  def find_root(self,x):
    if self.n[x]<0:
      return x
    else:
      self.n[x]=self.find_root(self.n[x])
      return self.n[x]
  def unite(self,x,y):
    x=self.find_root(x)
    y=self.find_root(y)
    if x==y:return
    elif self.r[x]>self.r[y]:
      self.n[x]+=self.n[y]
      self.n[y]=x
    else:
      self.n[y]+=self.n[x]
      self.n[x]=y
      if self.r[x]==self.r[y]:
        self.r[y]+=1
    self.siz-=1
  def root_same(self,x,y):
    return self.find_root(x)==self.find_root(y)
  def count(self,x):
    return -self.n[self.find_root(x)]
  def size(self):
    return self.siz

from collections import defaultdict
n,x,y=map(int,input().split())
mod=10**9+7
f=[1]
for i in range(1,n+7):f.append(f[-1]*i%mod)
cw=[list(map(int,input().split()))for _ in range(n)]
if n==1:exit(print(1))
if len(set(c for c,w in cw))==1:exit(print(1))
for i in range(n):cw[i][0]-=1
miw=[10**10]*n
miwi=[0]*n
for i in range(n):
  c,w=cw[i]
  if miw[c]>w:
    miw[c]=w
    miwi[c]=i
mminc=miw.index(min(miw))
temp=10**10
for i in range(n):
  if i!=mminc:temp=min(temp,miw[i])
sminc=miw.index(temp)
u=UnionFind(n)
for i in range(n):
  c,w=cw[i]
  if c==mminc:tc=sminc
  else:tc=mminc
  if miw[c]+w<=x:u.unite(miwi[c],i)
  if miw[tc]+w<=y:u.unite(miwi[tc],i)
d=[0]*n
for i in range(n):
  if i==u.find_root(i):d[i]=defaultdict(int)
for i in range(n):
  c,w=cw[i]
  d[u.find_root(i)][c]+=1
ans=1
for i in range(n):
  if i==u.find_root(i):
    anss=1
    co=0
    for j in d[i]:
      anss*=pow(f[d[i][j]],mod-2,mod)
      anss%=mod
      co+=d[i][j]
    anss*=f[co]
    ans=(ans*anss)%mod
print(ans)

Solution (Python):
import sys
readline = sys.stdin.readline
readlines = sys.stdin.readlines

MOD = 10**9 + 7

N,X,Y = map(int,readline().split())
CW = (tuple(int(x) for x in line.split()) for line in readlines())

C_to_W = [[] for _ in range(N+1)]
for c,w in CW:
    C_to_W[c].append(w)

for c in range(N+1):
    C_to_W[c].sort()

C_to_W.sort()

C_to_W = [x for x in C_to_W if x]

min_wt = C_to_W[0][0]
C_to_W = [x for x in C_to_W if x[0]+min_wt <= Y]

if len(C_to_W) <= 1:
    print(1)
    exit()

comp_size = [0] * (len(C_to_W))
for x in C_to_W[0]:
    if x+C_to_W[0][0] <= X or x + C_to_W[1][0] <= Y:
        comp_size[0] += 1

for i,arr in enumerate(C_to_W[1:],1):
    for x in arr:
        if x+min_wt <= Y or x+arr[0] <= X:
            comp_size[i] += 1

fact = [1] * (N+1)
for i in range(1,N+1):
    fact[i] = fact[i-1] * i % MOD

num = fact[sum(comp_size)]
den = 1
for x in comp_size:
    den *= fact[x]
    den %= MOD
answer = num * pow(den,MOD-2,MOD) % MOD
print(answer)