Submission #3402391

---

Source Code Expand

class Combination
  def initialize(n, mod)
    @mod = mod
    create_fact_mod(n)
    create_seq_inv_mod(n)
    create_fact_inv_mod(n)
  end

  def create_fact_mod(num_max)
    @fmod = Array.new(num_max + 1)
    @fmod[0] = 1
    @fmod[1] = 1
    (2..num_max).each do |i|
      @fmod[i] = (@fmod[i - 1] * i) % @mod
    end
  end

  def create_seq_inv_mod(num_max)
    @simod = Array.new(num_max + 1)
    @simod[0] = 1
    @simod[1] = 1
    (2..num_max).each do |i|
      @simod[i] = (@mod - @mod / i) * @simod[@mod % i] % @mod
    end
  end

  def create_fact_inv_mod(num_max)
    @fimod = Array.new(num_max + 1)
    @fimod[0] = 1
    @fimod[1] = 1
    (2..num_max).each do |i|
      @fimod[i] = (@fimod[i - 1] * @simod[i]) % @mod
    end
  end

  def comb_mod(n, k)
    @fmod[n] * @fimod[n - k] * @fimod[k] % @mod
  end

  def perm_mod(n, k)
    @fmod[n] * @fimod[n - k] % @mod
  end
end

H, W, A, B = gets.split.map(&:to_i)

M = [H - A, W - B].min
mod = 10**9 + 7
ans = 0

comb = Combination.new(H + W, mod)

M.times  do |i|
  h1 = H - A - i - 1
  w1 = B + i
  ans += comb.comb_mod(h1 + w1, h1) * comb.comb_mod(H - h1 + W - w1 - 2, H - h1 - 1)
  ans %= mod
end
puts ans

Submission Info

Judge Result