easyctf library

#!/usr/bin/env python3

mod = (10**9+7)

class vec:
  def __init__(self,a1,a2):
    self.a1 = a1 % mod
    self.a2 = a2 % mod

class mat:
  def __init__(self,a11,a12,a21,a22):
    self.a11 = a11 % mod
    self.a12 = a12 % mod
    self.a21 = a21 % mod
    self.a22 = a22 % mod
  def __mul__(self, other):
    if type(other) is mat:
      return mat(
        self.a11 * other.a11 + self.a12 * other.a21, # c_11
        self.a11 * other.a12 + self.a12 * other.a22, # c_12
        self.a21 * other.a11 + self.a22 * other.a21, # c_21
        self.a21 * other.a12 + self.a22 * other.a22, # c_22
      )
    else:
      return vec(
        self.a11 * other.a1 + self.a12 * other.a2,
        self.a21 * other.a1 + self.a22 * other.a2,
      )
  def __pow__(self, n):
    if n == 0:
      return mat(1,0,0,1)
    elif n == 1:
      return self
    else:
      a = mat(1,0,0,1)
      b = self
      while n > 1:
        if n%2 == 1:
          a = a * b
        b = b * b
        n //= 2
      return a*b

def library(n):
  m = mat(1,1,2,1) ** n
  v = m * vec(1, 0)
  return (v.a1 + v.a2) % mod

n = int(input())
print(library(n))