# require "/template" # require "./tuple/times" struct Tuple def times(&block) : Nil {% begin %} {% for i in 0...@type.size %} {% if @type[i].has_method?(:each) %} self[{{i}}].each do |i{{i}}| {% else %} self[{{i}}].times do |i{{i}}| {% end %} {% end %} yield({% for i in 0...@type.size %} i{{i}}, {% end %}) {% for i in 0...@type.size %} end {% end %} {% end %} end private class TimesIterator(T) include Iterator(T) def initialize(@n : T) tuple = {% begin %} { {% for i in 0...T.size %} T[{{i}}].zero, {% end %} } {% end %} @index = tuple.as(T) @first = true end def next if @first @first = false return @index end {% begin %} {% type = @type.type_vars[0] size = type.size %} {% for i in 1..size %} if @index[{{size - i}}] < @n[{{size - i}}] - 1 @index = { {% for j in 0...size %} {% if j < size - i %} @index[{{j}}], {% elsif j == size - i %} @index[{{j}}] + 1, {% else %} {{type[j]}}.zero, {% end %} {% end %} } return @index end {% end %} stop {% end %} end end def times TimesIterator(self).new(self) end end # require "./comparable/min_max" module Comparable(T) def min(x : T) self > x ? x : self end def max(x : T) self < x ? x : self end end # require "./array/new" class Array def self.new(sizes : Tuple(*T), initial_value) forall T {% begin %} {% for i in 0...T.size %} Array.new(sizes[{{i}}]) { {% end %} initial_value {% for i in 0...T.size %} } {% end %} {% end %} end def self.new(sizes : Tuple(*T), &block) forall T {% begin %} {% for i in 0...T.size %} Array.new(sizes[{{i}}]) { |index{{i}}| {% end %} yield({% for i in 0...T.size %} index{{i}}, {% end %}) {% for i in 0...T.size %} } {% end %} {% end %} end end # require "./array/change" class Array(T) def chmin(i : Int, value : T) (self[i] > value).tap do |f| self[i] = value if f end end protected def chmin(i : Int, *indexes, value) self[i].chmin(*indexes, value: value) end def chmin(indexes : Tuple, value) chmin(*indexes, value: value) end def chmax(i : Int, value : T) (self[i] < value).tap do |f| self[i] = value if f end end protected def chmax(i : Int, *indexes, value) self[i].chmax(*indexes, value: value) end def chmax(indexes : Tuple, value) chmax(*indexes, value: value) end end # require "./scanner" # ### Specifications # # ```plain # Inside input macro | Expanded code # -------------------------------------+--------------------------------------- # Uppercase string: Int32, Int64, etc. | {}.new(Scanner.s) # s | Scanner.s # c | Scanner.c # Other lowercase string: i, i64, etc. | Scanner.s.to_{} # operator[]: type[size] | Array.new(input(size)) { input(type) } # Tuple literal: {t1, t2, t3} | {input(t1), input(t2), input(t3)} # Array literal: [t1, t2, t3] | [input(t1), input(t2), input(t3)] # Range literal: t1..t2 | input(t1)..input(t2) # If: cond ? t1 : t2 | cond ? input(t1) : input(t2) # Assign: target = value | target = input(value) # ``` # # ### Examples # # Input: # ```plain # 5 3 # foo bar # 1 2 3 4 5 # ``` # ``` # n, m = input(Int32, Int64) # => {5, 10i64} # input(String, Char[m]) # => {"foo", ['b', 'a', 'r']} # input(Int32[n]) # => [1, 2, 3, 4, 5] # ``` # ``` # n, m = input(i, i64) # => {5, 10i64} # input(s, c[m]) # => {"foo", ['b', 'a', 'r']} # input(i[n]) # => [1, 2, 3, 4, 5] # ``` # # Input: # ```plain # 2 3 # 1 2 3 # 4 5 6 # ``` # # ``` # h, w = input(i, i) # => {2, 3} # input(i[h, w]) # => [[1, 2, 3], [4, 5, 6]] # ``` # ``` # input(i[i][i]) # => [[1, 2, 3], [4, 5, 6]] # ``` # # Input: # ```plain # 5 3 # 3 1 4 2 5 # 1 2 # 2 3 # 3 1 # ``` # ``` # n, m = input(i, i) # => {5, 3} # input(i.pred[n]) # => [2, 0, 3, 1, 4] # input({i - 1, i - 1}[m]) # => [{0, 1}, {1, 2}, {2, 0}] # ``` # # Input: # ```plain # 3 # 1 2 # 2 2 # 3 2 # ``` # ``` # input({tmp = i, tmp == 1 ? i : i.pred}[i]) # => [{1, 2}, {2, 1}, {3, 1}] # ``` # # Input: # ```plain # 3 # 1 2 # 2 3 # 3 1 # ``` # ``` # n = input(i) # input_column({Int32, Int32}, n) # => {[1, 2, 3], [2, 3, 1]} # ``` class Scanner private def self.skip_to_not_space peek = STDIN.peek not_space = peek.index { |x| x != 32 && x != 10 } || peek.size STDIN.skip(not_space) end def self.c skip_to_not_space STDIN.read_char.not_nil! end def self.s skip_to_not_space peek = STDIN.peek if index = peek.index { |x| x == 32 || x == 10 } STDIN.skip(index + 1) return String.new(peek[0, index]) end String.build do |buffer| loop do buffer.write peek STDIN.skip(peek.size) peek = STDIN.peek break if peek.empty? if index = peek.index { |x| x == 32 || x == 10 } buffer.write peek[0, index] STDIN.skip(index) break end end end end end macro internal_input(type, else_ast) {% if Scanner.class.has_method?(type.id) %} Scanner.{{type.id}} {% elsif type.stringify == "String" %} Scanner.s {% elsif type.stringify == "Char" %} Scanner.c {% elsif type.stringify =~ /[A-Z][a-z0-9_]*/ %} {{type.id}}.new(Scanner.s) {% elsif String.has_method?("to_#{type}".id) %} Scanner.s.to_{{type.id}} {% else %} {{else_ast}} {% end %} end macro internal_input_array(type, args) {% for i in 0...args.size %} %size{i} = input({{args[i]}}) {% end %} {% begin %} {% for i in 0...args.size %} Array.new(%size{i}) { {% end %} input({{type.id}}) {% for i in 0...args.size %} } {% end %} {% end %} end macro input(type) {% if type.is_a?(Call) %} {% if type.receiver.is_a?(Nop) %} internal_input( {{type.name}}, {{type.name}}( {% for argument in type.args %} input({{argument}}), {% end %} ) ) {% elsif type.name.stringify == "[]" %} internal_input_array({{type.receiver}}, {{type.args}}) {% else %} input({{type.receiver}}).{{type.name.id}}( {% for argument in type.args %} input({{argument}}), {% end %} ) {{type.block}} {% end %} {% elsif type.is_a?(TupleLiteral) %} { {% for i in 0...type.size %} input({{type[i]}}), {% end %} } {% elsif type.is_a?(ArrayLiteral) %} [ {% for i in 0...type.size %} input({{type[i]}}), {% end %} ] {% elsif type.is_a?(RangeLiteral) %} Range.new(input({{type.begin}}), input({{type.end}}), {{type.excludes_end?}}) {% elsif type.is_a?(If) %} {{type.cond}} ? input({{type.then}}) : input({{type.else}}) {% elsif type.is_a?(Assign) %} {{type.target}} = input({{type.value}}) {% else %} internal_input({{type.id}}, {{type.id}}) {% end %} end macro input(*types) { {% for type in types %} input({{type}}), {% end %} } end macro input_column(types, size) {% for type, i in types %} %array{i} = Array({{type}}).new({{size}}) {% end %} {{size}}.times do {% for type, i in types %} %array{i} << input({{type}}) {% end %} end { {% for type, i in types %} %array{i}, {% end %} } end # require "/math/mint" macro static_modint(name, mod) struct {{name}} MOD = {{mod}}i64 def self.zero new end def self.raw(value : Int64) result = new result.value = value result end macro [](*nums) {% verbatim do %} Array({{@type}}).build({{nums.size}}) do |%buffer| {% for num, i in nums %} %buffer[{{i}}] = {{@type}}.new({{num}}) {% end %} {{nums.size}} end {% end %} end getter value : Int64 def initialize @value = 0i64 end def initialize(value) @value = value.to_i64 % MOD end def initialize(m : self) @value = m.value end protected def value=(value : Int64) @value = value end def ==(m : self) value == m.value end def ==(m) value == m end def + : self self end def - : self self.class.raw(value != 0 ? MOD &- value : 0i64) end def +(v) self + self.class.new(v) end def +(m : self) x = value &+ m.value x &-= MOD if x >= MOD self.class.raw(x) end def -(v) self - self.class.new(v) end def -(m : self) x = value &- m.value x &+= MOD if x < 0 self.class.raw(x) end def *(v) self * self.class.new(v) end def *(m : self) self.class.new(value &* m.value) end def /(v) self / self.class.new(v) end def /(m : self) raise DivisionByZeroError.new if m.value == 0 a, b, u, v = m.value, MOD, 1i64, 0i64 while b != 0 t = a // b a &-= t &* b a, b = b, a u &-= t &* v u, v = v, u end self.class.new(value &* u) end def //(v) self / v end def **(exponent : Int) t, res = self, self.class.raw(1i64) while exponent > 0 res *= t if exponent & 1 == 1 t *= t exponent >>= 1 end res end {% for op in %w[< <= > >=] %} def {{op.id}}(other) raise NotImplementedError.new({{op}}) end {% end %} def inv self.class.raw(1) // self end def succ self.class.raw(value != MOD &- 1 ? value &+ 1 : 0i64) end def pred self.class.raw(value != 0 ? value &- 1 : MOD &- 1) end def abs self end def abs2 self * self end def to_i64 : Int64 value end delegate to_s, to: @value delegate inspect, to: @value end {% to = ("to_" + name.stringify.downcase.gsub(/mint|modint/, "m")).id %} struct Int {% for op in %w[+ - * / //] %} def {{op.id}}(value : {{name}}) {{to}} {{op.id}} value end {% end %} {% for op in %w[< <= > >=] %} def {{op.id}}(m : {{name}}) raise NotImplementedError.new({{op}}) end {% end %} def {{to}} : {{name}} {{name}}.new(self) end end class String def {{to}} : {{name}} {{name}}.new(self) end end end static_modint(Mint, 1000000007) static_modint(Mint2, 998244353) # require "atcoder/Prime" # ac-library.cr by hakatashi https://github.com/google/ac-library.cr # # Copyright 2021 Google LLC # # Licensed under the Apache License, Version 2.0 (the "License"); # you may not use this file except in compliance with the License. # You may obtain a copy of the License at # # https://www.apache.org/licenses/LICENSE-2.0 # # Unless required by applicable law or agreed to in writing, software # distributed under the License is distributed on an "AS IS" BASIS, # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. # See the License for the specific language governing permissions and # limitations under the License. # require "./Math.cr" # ac-library.cr by hakatashi https://github.com/google/ac-library.cr # # Copyright 2021 Google LLC # # Licensed under the Apache License, Version 2.0 (the "License"); # you may not use this file except in compliance with the License. # You may obtain a copy of the License at # # https://www.apache.org/licenses/LICENSE-2.0 # # Unless required by applicable law or agreed to in writing, software # distributed under the License is distributed on an "AS IS" BASIS, # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. # See the License for the specific language governing permissions and # limitations under the License. module AtCoder # Implements [ACL's Math library](https://atcoder.github.io/ac-library/master/document_en/math.html) module Math def self.extended_gcd(a, b) last_remainder, remainder = a.abs, b.abs x, last_x, y, last_y = 0_i64, 1_i64, 1_i64, 0_i64 while remainder != 0 new_last_remainder = remainder quotient, remainder = last_remainder.divmod(remainder) last_remainder = new_last_remainder x, last_x = last_x - quotient * x, x y, last_y = last_y - quotient * y, y end return last_remainder, last_x * (a < 0 ? -1 : 1) end # Implements atcoder::inv_mod(value, modulo). def self.inv_mod(value, modulo) gcd, inv = extended_gcd(value, modulo) if gcd != 1 raise ArgumentError.new("#{value} and #{modulo} are not coprime") end inv % modulo end # Simplified AtCoder::Math.pow_mod with support of Int64 def self.pow_mod(base, exponent, modulo) if exponent == 0 return base.class.zero + 1 end if base == 0 return base end b = exponent > 0 ? base : inv_mod(base, modulo) e = exponent.abs ret = 1_i64 while e > 0 if e % 2 == 1 ret = mul_mod(ret, b, modulo) end b = mul_mod(b, b, modulo) e //= 2 end ret end # Caluculates a * b % mod without overflow detection @[AlwaysInline] def self.mul_mod(a : Int64, b : Int64, mod : Int64) if mod < Int32::MAX return a * b % mod end # 31-bit width a_high = (a >> 32).to_u64 # 32-bit width a_low = (a & 0xFFFFFFFF).to_u64 # 31-bit width b_high = (b >> 32).to_u64 # 32-bit width b_low = (b & 0xFFFFFFFF).to_u64 # 31-bit + 32-bit + 1-bit = 64-bit c = a_high * b_low + b_high * a_low c_high = c >> 32 c_low = c & 0xFFFFFFFF # 31-bit + 31-bit res_high = a_high * b_high + c_high # 32-bit + 32-bit res_low = a_low * b_low res_low_high = res_low >> 32 res_low_low = res_low & 0xFFFFFFFF # Overflow if res_low_high + c_low >= 0x100000000 res_high += 1 end res_low = (((res_low_high + c_low) & 0xFFFFFFFF) << 32) | res_low_low (((res_high.to_i128 << 64) | res_low) % mod).to_i64 end @[AlwaysInline] def self.mul_mod(a, b, mod) typeof(mod).new(a.to_i64 * b % mod) end # Implements atcoder::crt(remainders, modulos). def self.crt(remainders, modulos) raise ArgumentError.new unless remainders.size == modulos.size total_modulo = 1_i64 answer = 0_i64 remainders.zip(modulos).each do |(remainder, modulo)| gcd, p = extended_gcd(total_modulo, modulo) if (remainder - answer) % gcd != 0 return 0_i64, 0_i64 end tmp = (remainder - answer) // gcd * p % (modulo // gcd) answer += total_modulo * tmp total_modulo *= modulo // gcd end return answer % total_modulo, total_modulo end # Implements atcoder::floor_sum(n, m, a, b). def self.floor_sum(n, m, a, b) n, m, a, b = n.to_i64, m.to_i64, a.to_i64, b.to_i64 res = 0_i64 if a < 0 a2 = a % m res -= n * (n - 1) // 2 * ((a2 - a) // m) a = a2 end if b < 0 b2 = b % m res -= n * ((b2 - b) // m) b = b2 end res + floor_sum_unsigned(n, m, a, b) end private def self.floor_sum_unsigned(n, m, a, b) res = 0_i64 loop do if a >= m res += n * (n - 1) // 2 * (a // m) a = a % m end if b >= m res += n * (b // m) b = b % m end y_max = a * n + b break if y_max < m n = y_max // m b = y_max % m m, a = a, m end res end end end module AtCoder # Implements [Ruby's Prime library](https://ruby-doc.com/stdlib/libdoc/prime/rdoc/Prime.html). # # ``` # AtCoder::Prime.first(7) # => [2, 3, 5, 7, 11, 13, 17] # ``` module Prime extend self include Enumerable(Int64) @@primes = [ 2_i64, 3_i64, 5_i64, 7_i64, 11_i64, 13_i64, 17_i64, 19_i64, 23_i64, 29_i64, 31_i64, 37_i64, 41_i64, 43_i64, 47_i64, 53_i64, 59_i64, 61_i64, 67_i64, 71_i64, 73_i64, 79_i64, 83_i64, 89_i64, 97_i64, 101_i64, ] def each index = 0 loop do yield get_nth_prime(index) index += 1 end end def prime_division(value : Int) raise DivisionByZeroError.new if value == 0 int = typeof(value) factors = [] of Tuple(typeof(value), typeof(value)) if value < 0 value = value.abs factors << {int.new(-1), int.new(1)} end until prime?(value) || value == 1 factor = value until prime?(factor) factor = find_factor(factor) end count = 0 while value % factor == 0 value //= factor count += 1 end factors << {int.new(factor), int.new(count)} end if value > 1 factors << {value, int.new(1)} end factors.sort_by! { |(factor, _)| factor } end private def find_factor(n : Int) # Factor of 4 cannot be discovered by Pollard's Rho with f(x) = x^x+1 if n == 4 typeof(n).new(2) else pollard_rho(n).not_nil! end end # Get single factor by Pollard's Rho Algorithm private def pollard_rho(n : Int) typeof(n).new(1).upto(n) do |i| x = i y = pollard_random_f(x, n) loop do x = pollard_random_f(x, n) y = pollard_random_f(pollard_random_f(y, n), n) gcd = (x - y).gcd(n) if gcd == n break end if gcd != 1 return gcd end end end end private def pollard_random_f(n : Int, mod : Int) (AtCoder::Math.mul_mod(n, n, mod) + 1) % mod end private def extract_prime_division_base(prime_divisions_class : Array({T, T}).class) forall T T end def int_from_prime_division(prime_divisions : Array({Int, Int})) int_class = extract_prime_division_base(prime_divisions.class) prime_divisions.reduce(int_class.new(1)) { |i, (factor, exponent)| i * factor ** exponent } end def prime?(value : Int) # Obvious patterns return false if value < 2 return true if value <= 3 return false if value.even? return true if value < 9 if value < 0xffff return false unless typeof(value).new(30).gcd(value % 30) == 1 7.step(by: 30, to: value) do |base| break if base * base > value if {0, 4, 6, 10, 12, 16, 22, 24}.any? { |i| value % (base + i) == 0 } return false end end return true end miller_rabin(value.to_i64) end private def miller_rabin(value) d = value - 1 s = 0_i64 until d.odd? d >>= 1 s += 1 end miller_rabin_bases(value).each do |base| next if base == value x = AtCoder::Math.pow_mod(base.to_i64, d, value) next if x == 1 || x == value - 1 is_composite = s.times.all? do x = AtCoder::Math.mul_mod(x, x, value) x != value - 1 end return false if is_composite end true end # We can reduce time complexity of Miller-Rabin tests by testing against # predefined bases which is enough to test against primarity in the given range. # https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test # ameba:disable Metrics/CyclomaticComplexity private def miller_rabin_bases(value) case when value < 1_373_653_i64 [2, 3] when value < 9_080_191_i64 [31, 73] when value < 25_326_001_i64 [2, 3, 5] when value < 3_215_031_751_i64 [2, 3, 5, 7] when value < 4_759_123_141_i64 [2, 7, 61] when value < 1_122_004_669_633_i64 [2, 13, 23, 1662803] when value < 2_152_302_898_747_i64 [2, 3, 5, 7, 11] when value < 3_474_749_660_383_i64 [2, 3, 5, 7, 11, 13] when value < 341_550_071_728_321_i64 [2, 3, 5, 7, 11, 13, 17] when value < 3_825_123_056_546_413_051_i64 [2, 3, 5, 7, 11, 13, 17, 19, 23] else [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37] end end private def get_nth_prime(n) while @@primes.size <= n generate_primes end @@primes[n] end # Doubles the size of the cached prime array and performs the # Sieve of Eratosthenes on it. private def generate_primes new_primes_size = @@primes.size < 1_000_000 ? @@primes.size : 1_000_000 new_primes = Array(Int64).new(new_primes_size) { |i| @@primes.last + (i + 1) * 2 } new_primes_max = new_primes.last @@primes.each do |prime| next if prime == 2 break if prime * prime > new_primes_max # Here I use the technique of the Sieve of Sundaram. We can # only test against the odd multiple of the given prime. # min_composite is the minimum number that is greater than # the last confirmed prime, and is an odd multiple of # the given prime. min_multiple = ((@@primes.last // prime + 1) // 2 * 2 + 1) * prime min_multiple.step(by: prime * 2, to: new_primes_max) do |multiple| index = new_primes_size - (new_primes_max - multiple) // 2 - 1 new_primes[index] = 0_i64 end end @@primes.concat(new_primes.reject(0_i64)) end private struct EachDivisor(T) include Enumerable(T) def initialize(@exponential_factors : Array(Array(T))) end def each Array.each_product(@exponential_factors) do |factors| yield factors.reduce { |a, b| a * b } end end end # Returns an enumerator that iterates through the all positive divisors of # the given number. **The order is not guaranteed.** # Not in the original Ruby's Prime library. # # ``` # AtCoder::Prime.each_divisor(20) do |n| # puts n # end # => Puts 1, 2, 4, 5, 10, and 20 # # AtCoder::Prime.each_divisor(10).map { |n| 1.0 / n }.to_a # => [1.0, 0.5, 0.2, 0.1] # ``` def each_divisor(value : Int) raise ArgumentError.new unless value > 0 factors = prime_division(value) if value == 1 exponential_factors = [[value]] else exponential_factors = factors.map do |(factor, count)| cnt = typeof(value).zero + 1 Array(typeof(value)).new(count + 1) do |i| cnt_copy = cnt if i < count cnt *= factor end cnt_copy end end end EachDivisor(typeof(value)).new(exponential_factors) end # :ditto: def each_divisor(value : T, &block : T ->) each_divisor(value).each(&block) end end end struct Int def prime? AtCoder::Prime.prime?(self) end end def combination(n, m) x = 1.to_m (n - m + 1..n).each { |i| x *= i } (1..m).each { |i| x /= i } x end n, k = input(i64, i64) puts AtCoder::Prime.prime_division(n).reduce(1.to_m) { |ans, (p, c)| ans * combination(k + c, c) }