# require "math/Sieve" class Sieve getter size : Int32 getter factor : Array(Int32) getter primes : Array(Int32) def initialize(@size) @factor = Array(Int32).new(@size + 1, 0) @primes = [] of Int32 sqrt_size = Math.sqrt(@size).to_i + 1 (2..size).each do |x| next unless @factor[x] == 0 @factor[x] = x @primes << x next if sqrt_size < x (x * x).step(to: size, by: x) { |y| @factor[y] = x if @factor[y] == 0 } end end def prime?(x) factor[x] == x end private class PrimeDivisionIterator include Iterator({Int32, Int32}) def initialize(@current : Int32, @factor : Array(Int32)) end def next return stop if @current == 1 element = @factor[@current] count = 0 while @current != 1 && @factor[@current] == element count += 1 @current //= element end {element, count} end end def prime_division(x) PrimeDivisionIterator.new(x, factor) end def each_factor(x, &) : Nil while x > 1 element = @factor[x] count = 0 while x != 1 && @factor[x] == element count += 1 x //= element end yield(element, count) end end end # require "math/Mint" macro static_modint(name, mod) struct {{name}} MOD = Int64.new({{mod}}) def self.zero new end def self.raw(value : Int64) result = new result.value = value result end @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 getter value : Int64 def + : self self end def - : self self.class.raw(value != 0 ? MOD &- value : 0i64) end def +(v) self + v.to_m end def +(m : self) x = value &+ m.value x &-= MOD if x >= MOD self.class.raw(x) end def -(v) self - v.to_m end def -(m : self) x = value &- m.value x &+= MOD if x < 0 self.class.raw(x) end def *(v) self * v.to_m end def *(m : self) self.class.new(value &* m.value) end def /(v) self / v.to_m end def /(m : self) raise DivisionByZeroError.new if m.value == 0 a, b, u, v = m.to_i64, 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 def ==(m : self) value == m.value end def ==(m : Int) raise NotImplementedError.new("==") end {% for op in %w[< <= > >=] %} def {{op.id}}(other) raise NotImplementedError.new({{op}}) end {% 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 to_i64 : Int64 value end delegate to_s, to: @value delegate inspect, to: @value end struct Int {% for op in %w[+ - * / //] %} def {{op.id}}(value : {{name}}) to_m {{op.id}} value end {% end %} {% for op in %w[== != < <= > >=] %} def {{op.id}}(m : {{name}}) raise NotImplementedError.new({{op}}) end {% end %} def to_m : {{name}} {{name}}.new(self) end end class String def to_m : {{name}} {{name}}.new(self) end end end static_modint(Mint, 998244353) n = read_line.to_i sieve = Sieve.new(n) max = Hash(Int32, Int32).new(0) (1...n).each do |x| hash = Hash(Int32, Int32).new(0) sieve.each_factor(x) { |elem, cnt| hash[elem] += cnt } sieve.each_factor(n - x) { |elem, cnt| hash[elem] += cnt } hash.each { |elem, cnt| max[elem] = {max[elem], cnt}.max } end puts max.reduce(Mint.new(1)) { |acc, (elem, cnt)| acc * Mint.new(elem)**cnt }