# require "crystal/mod_int" # modint struct ModInt MAX = 100_000 MOD = 10_i64 ** 9 + 7 # MOD = 998_244_353_i64 class_getter f = Array(ModInt).new(MAX) getter v : Int64 def self.f(n) f << 1.to_m if f.empty? f.size.upto(n) do |i| f << f.last * i end f[n] end def self.p(n, k) return ModInt.zero if n < k n.f // (n - k).f end def self.c(n, k) return ModInt.zero if n < k p(n, k) // k.f end def self.h(n, k) c(n + k - 1, k) end def initialize(v) @v = v.to_i64 % MOD end {% for op in %w(+ - *) %} def {{op.id}}(b) ModInt.new(v {{op.id}} (b.to_i64 % MOD)) end {% end %} def **(b) a = self ans = 1.to_m while b > 0 ans *= a if b.odd? b //= 2 a *= a end return ans end def inv self ** (MOD - 2) end def //(b) self * b.to_m.inv end def self.zero new(0) end def ==(b) v == b.to_i64 end def to_m self end delegate to_i64, to: v delegate to_s, to: v delegate inspect, to: v end struct Int def to_m ModInt.new(to_i64) end def f ModInt.f(self) end def p(k) ModInt.p(self, k) end def c(k) ModInt.c(self, k) end def h(k) ModInt.h(self, k) end end # require "crystal/matrix" class Matrix(T) getter n : Int32 getter a : Array(Array(T)) def self.zero(n) new(n) { T.zero } end def self.eye(n) new(n) { |i, j| i == j ? T.zero + 1 : T.zero } end def initialize(@n) @a = Array.new(n) { |i| Array.new(n) { |j| yield i, j } } end def initialize(@a) @n = a.size end def *(b : self) : self Matrix(T).new(n) do |i, j| ans = T.zero n.times do |k| ans += self[i, k] * b[k, j] end ans end end def **(k : Int) : self ans = Matrix(T).eye(n) m = Math.ilogb(k) + 1 b = dup m.times do |i| ans *= b if (k>>i).odd? b *= b end ans end @[AlwaysInline] def [](i,j) a[i][j] end @[AlwaysInline] def []=(i,j,x) a[i][j] = x end def ==(b : self) : Bool n.times.all? do |i| n.times.all? do |j| self[i, j] == b[i, j] end end end end Z = 0.to_m E = 1.to_m A = Matrix(ModInt).new([[E,E],[E,Z]]) def f(n) (A ** n)[0,0] end n = gets.to_s.to_i64 ans = f(n) * f(n - 1) pp ans