Submission #3253308

Source Code Expand

Copy
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 create_mod_tables(n)
    create_fact_mod(n)
    create_seq_inv_mod(n)
    create_fact_inv_mod(n)
end

def comb_mod(n, k)
    return $fmod[n] * $fimod[n - k] * $fimod[k] % MOD
end


require 'prime'
N, M = gets.split.map(&:to_i)
pn = Prime.prime_division(M).map{|a| a[1]}
MOD = 10**9+7

create_mod_tables(N+100)

ans = 1
pn.each do |num|
    ans *= comb_mod(N-1+num, num)
    ans %= MOD
end
puts ans

Submission Info

Submission Time
Task D - Factorization
User betrue12
Language Ruby (2.3.3)
Score 400
Code Size 1042 Byte
Status
Exec Time 57 ms
Memory 4348 KB

Test Cases

Set Name Score / Max Score Test Cases
All 400 / 400 0_small_1, 0_small_2, 0_small_3, 1_large_1, 1_large_2, 1_large_3, 2_large_1, 2_large_2, 3_prime_1, 3_prime_10, 3_prime_11, 3_prime_12, 3_prime_13, 3_prime_14, 3_prime_15, 3_prime_16, 3_prime_17, 3_prime_18, 3_prime_19, 3_prime_2, 3_prime_20, 3_prime_21, 3_prime_22, 3_prime_3, 3_prime_4, 3_prime_5, 3_prime_6, 3_prime_7, 3_prime_8, 3_prime_9, 4_hand_1, 4_hand_2, 4_hand_3, sample_01, sample_02, sample_03
Sample 0 / 0 sample_01, sample_02, sample_03
Case Name Status Exec Time Memory
0_small_1 10 ms 1916 KB
0_small_2 10 ms 2044 KB
0_small_3 10 ms 2044 KB
1_large_1 48 ms 4092 KB
1_large_2 30 ms 3068 KB
1_large_3 49 ms 4220 KB
2_large_1 52 ms 4348 KB
2_large_2 53 ms 4348 KB
3_prime_1 53 ms 4348 KB
3_prime_10 52 ms 4348 KB
3_prime_11 51 ms 4348 KB
3_prime_12 51 ms 4348 KB
3_prime_13 51 ms 4348 KB
3_prime_14 53 ms 4348 KB
3_prime_15 51 ms 4348 KB
3_prime_16 52 ms 4348 KB
3_prime_17 51 ms 4348 KB
3_prime_18 51 ms 4348 KB
3_prime_19 51 ms 4348 KB
3_prime_2 57 ms 4348 KB
3_prime_20 51 ms 4348 KB
3_prime_21 51 ms 4348 KB
3_prime_22 57 ms 4348 KB
3_prime_3 53 ms 4348 KB
3_prime_4 53 ms 4348 KB
3_prime_5 51 ms 4348 KB
3_prime_6 53 ms 4348 KB
3_prime_7 53 ms 4348 KB
3_prime_8 53 ms 4348 KB
3_prime_9 57 ms 4348 KB
4_hand_1 51 ms 4348 KB
4_hand_2 51 ms 4348 KB
4_hand_3 10 ms 2044 KB
sample_01 10 ms 1916 KB
sample_02 10 ms 1916 KB
sample_03 53 ms 4348 KB