Problem p02555 (python)

Fixed submission:
def main(sample_file = ''):

    """ convenient functions
    # for i, a in enumerate(iterable)
    # q, mod = divmod(a, b)
    # divmod(x, y) returns the tuple (x//y, x%y)
    # Higher-order function: reduce(operator.mul, xyz_count, 1)
    # manage median(s) using two heapq https://atcoder.jp/contests/abc127/tasks/abc127_f
    """

    """convenient decorator
    # @functools.lru_cache():
    # to facilitate use of recursive function
        # ex:
        # from functools import lru_cache
        # import sys
        # sys.setrecursionlimit(10**9)
        # @lru_cache(maxsize=None)
        # def fib(n):
        #     if n < 2:
        #         return n
        #     return fib(n-1) + fib(n-2)
        # print(fib(1000))
    """
    
    # import numpy as np
    import sys
    sys.setrecursionlimit(10**7)
    from itertools import accumulate, combinations, permutations, product, combinations_with_replacement # https://docs.python.org/ja/3/library/itertools.html
    # accumulate() returns iterator! to get list: list(accumulate())
    from math import factorial, ceil, floor, sqrt
    def factorize(n):
        """return the factors of the Arg and count of each factor
        
        Args:
            n (long): number to be resolved into factors
        
        Returns:
            list of tuples: factorize(220) returns [(2, 2), (5, 1), (11, 1)]
        """
        fct = []  # prime factor
        b, e = 2, 0  # base, exponent
        while b * b <= n:
            while n % b == 0:
                n = n // b
                e = e + 1
            if e > 0:
                fct.append((b, e))
            b, e = b + 1, 0
        if n > 1:
            fct.append((n, 1))
        return fct
    def combinations_count(n, r):   
        """Return the number of selecting r pieces of items from n kinds of items.
        
        Args:
            n (long): number
            r (long): number
        
        Raises:
            Exception: not defined when n or r is negative
        
        Returns:
            long: number
        """
        # TODO: How should I do when n - r is negative?
        if n < 0 or r < 0:
            raise Exception('combinations_count(n, r) not defined when n or r is negative')
        if n - r < r: r = n - r
        if r < 0: return 0
        if r == 0: return 1
        if r == 1: return n
        numerator = [n - r + k + 1 for k in range(r)]
        denominator = [k + 1 for k in range(r)]
        for p in range(2,r+1):
            pivot = denominator[p - 1]
            if pivot > 1:
                offset = (n - r) % p
                for k in range(p-1,r,p):
                    numerator[k - offset] /= pivot
                    denominator[k] /= pivot
        result = 1
        for k in range(r):
            if numerator[k] > 1:
                result *= int(numerator[k])
        return result
    def combinations_with_replacement_count(n, r):
        """Return the number of selecting r pieces of items from n kinds of items allowing individual elements to be repeated more than once.
        
        Args:
            n (long): number
            r (long): number
        
        Raises:
            Exception: not defined when n or r is negative
        
        Returns:
            long: number
        """
        if n < 0 or r < 0:
            raise Exception('combinations_with_replacement_count(n, r) not defined when n or r is negative')
        elif n == 0:
            return 1
        else:
            return combinations_count(n + r - 1, r)
    from bisect import bisect_left, bisect_right
    from collections import deque, Counter, defaultdict # https://docs.python.org/ja/3/library/collections.html#collections.deque
    from heapq import heapify, heappop, heappush, heappushpop, heapreplace,nlargest,nsmallest # https://docs.python.org/ja/3/library/heapq.html
    from copy import deepcopy, copy # https://docs.python.org/ja/3/library/copy.html
    import operator
    from operator import itemgetter #sort 
    # ex1: List.sort(key=itemgetter(1))
    # ex2: sorted(tuples, key=itemgetter(1,2))
    from functools import reduce, lru_cache
    def chmin(x, y):
        """change minimum
        if x > y, x = y and return (x, True).
        convenient when solving problems of dp[i]
        
        Args:
            x (long): current minimum value
            y (long): potential minimum value
        
        Returns:
            (x, bool): (x, True) when updated, else (x, False)
        """
        if x > y:
            x = y
            return (x, True)
        else:
            return (x, False)
    def chmax(x, y):
        """change maximum
        if x < y, x = y and return (x, True).
        convenient when solving problems of dp[i]
        
        Args:
            x (long): current maximum value
            y (long): potential maximum value
        
        Returns:
            (x, bool): (x, True) when updated, else (x, False)
        """
        if x < y:
            x = y
            return (x, True)
        else:
            return (x, False)

    from fractions import gcd
    def gcd(a,b):
        # from fractions import gcd # Deprecated since version 3.5: Use math.gcd() instead.
        # => 最近の環境でfractions.gcdを使うとTLEする。
        if a<b:
            a, b = b, a
        while a%b !=0 :
            a, b = b, a%b
        return b

    # def gcd(p,q):
    #     while q != 0:
    #         r = p % q
    #         p = q
    #         q = r
    #     return p

    def gcds(numbers):
        return reduce(gcd, numbers)
    def lcm(x, y):
        return (x * y) // gcd(x, y)
    def lcms(numbers):
        return reduce(lcm, numbers, 1)
    def make_divisors(n, reversed=False):
        """create list of divisors
        
        Args:
            number (int): number from which list of divisors is created
            reversed (bool, optional): ascending order if False. Defaults to False.
        
        Returns:
            list: list of divisors
        """
        divisors = set()
        for i in range(1, int(n**0.5)+1):
            if n % i == 0:
                divisors.add(i)
                divisors.add(n//i)
        return sorted(list(divisors),reverse=reversed)

    # Eratosthenesの篩により、整数end未満の素数を列挙する
    def sieve_of_eratosthenes(end, typecode="L"):
        # len(sieve_of_eratosthenes(10**7)) => 664579; 514ms in pypy
        # len(sieve_of_eratosthenes(10**6)) => 78498; 134ms in pypy

        # https://hamukichi.hatenablog.jp/entry/2016/02/17/215948#Eratosthenes%E3%81%AE%E7%AF%A9%E3%81%A8%E5%8C%BA%E9%96%93%E7%AF%A9
        import array
        import textwrap
        assert end > 1
        # 整数iが素数であるかをis_prime[i]が示す
        # 最初はすべてTrueで初期化しておく
        # 最終的にprimesではなくこれを返してもよい
        is_prime = array.array("B", (True for i in range(end)))
        # 0, 1はいずれも素数ではない
        is_prime[0] = False
        is_prime[1] = False
        # 素数を格納する配列
        primes = array.array(typecode)
        # 篩う
        for i in range(2, end):
            if is_prime[i]:
                primes.append(i)
                for j in range(2 * i, end, i):
                    is_prime[j] = False  # 素数ではないため除外する
        return primes

    class PrimeFactorization:
        '''初期化にO(NloglogN)/ 因数分解クエリをO(log(k))/ 素数判定クエリをO(1)
        >>> pf = PrimeFactorization(100)
        >>> pf.query(100)
        ((2, 2), (5, 2))
        
        '''
        # 自分で実装した。
        # https://atcoder.jp/contests/abc177/editorial/82
        # 高速素因数分解
        # 問題： A 以下の数が N 個与えられる。全て素因数分解せよ。
        # 前計算としてエラトステネスの篩を行い、「その数をふるい落とした素数」を配列 D に記録します。
        # 例えば D[4]=D[6]=2,D[35]=5 です。x が素数のときは D[x]=x としておきます。この配列はエラトステネスの篩と同様 O(AloglogA) で構築できます。
        # D[x] は x を割り切る最小の素数なので、この配列 D を利用すると素因数分解を行うときに「試し割り」をする必要がなくなり(D[x]で割ればよい)、1つの数の素因数分解が素因数の個数である O(logA) でできるようになります。
        def __init__(self, Num=10**6):
            from collections import defaultdict
            from math import floor
            self.Num = Num
            self.D = [-1] * (Num+1)
            for i in range(2, Num+1):
                if self.D[i] != -1:
                    continue
                self.D[i] = i
                for j in range(1, floor(Num/i)+1):
                    if self.D[j*i] != -1:
                        continue
                    else:
                        self.D[j*i] = i
        
        def query(self, k):
            ans = defaultdict(int)
            tmp = k
            while self.D[tmp] != -1:
                div = self.D[tmp]
                ans[div] += 1
                tmp = tmp//div
            return tuple(ans.items())
        
        def is_prime(self, k):
            return k == self.D[k]

    # first create factorial_list
    # fac_list = modfactorial_list(n)
    INF = 10 ** 18
    MOD = 10 ** 9 + 7
    AtoZ = list('abcdefghijklmnopqrsruvwxyz') # 26
    modpow = lambda a, n, p = MOD: pow(a, n, p) # Recursive function in python is slow!
    def modinv(a, p = MOD):
        # evaluate reciprocal using Fermat's little theorem:
        # a**(p-1) is identical to 1 (mod p) when a and p is coprime
        return modpow(a, p-2, p)
    def modinv_list(n, p = MOD):
        if n <= 1:
            return [0,1][:n+1]
        else:
            inv_t = [0,1]
            for i in range(2, n+1):
                inv_t += [inv_t[p % i] * (p - int(p / i)) % p]
            return inv_t
    def modfactorial_list(n, p = MOD):
        if n == 0:
            return [1]
        else:
            l = [0] * (n+1)
            tmp = 1
            for i in range(1, n+1):
                tmp = tmp * i % p
                l[i] = tmp
            return l
    def modcomb(n, k, fac_list = [], p = MOD):
        # fac_list = modfactorial_list(100)
        # print(modcomb(100, 5, modfactorial_list(100)))
        from math import factorial
        if n < 0 or k < 0 or n < k: return 0
        if n == 0 or k == 0: return 1
        if len(fac_list) <= n:
            a = factorial(n) % p
            b = factorial(k) % p
            c = factorial(n-k) % p
        else:
            a = fac_list[n]
            b = fac_list[k]
            c = fac_list[n-k]
        return (a * modpow(b, p-2, p) * modpow(c, p-2, p)) % p
    def modadd(a, b, p = MOD):
        return (a + b) % MOD
    def modsub(a, b, p = MOD):
        return (a - b) % p
    def modmul(a, b, p = MOD):
        return ((a % p) * (b % p)) % p
    def moddiv(a, b, p = MOD):
        return modmul(a, modpow(b, p-2, p))

    class UnionFindTree:
        """union find tree class
        TODO: fix this description...
        how to use (example):
        >>  uf = UnionFindTree(N) 
        >>  if uf.find_root(a) == uf.find_root(b):
        >>      do something like:
        >>      pass
        >>  else:
        >>      do something like:
        >>      L[find_root(a)] = L[find_root(a)] + L[find_root(b)]
        >>      L[find_root(b)] = L[find_root(a)]
        >>      
        >>      uf.unite(a, b)
        """
        def __init__(self, N):
            self.root = [-1] * (N+1)
            self.rank   = [0]  * (N+1)
            self.connected_num = [1] * (N+1)
    
        def find_root(self,x):
            root = self.root
            while root[x] != -1:
                x = root[x]
            return x
    
        def unite(self,x,y):
            root = self.root
            rank = self.rank
            connected_num = self.connected_num
            find_root = self.find_root
    
            rx = find_root(x)
            ry = find_root(y)
            if rx != ry:
                if rank[rx] < rank[ry]:
                    root[rx] = ry
                    rx,ry = ry,rx
                else:
                    if rank[rx] == rank[ry]:
                        rank[rx] += 1
                    root[ry] = rx       
                connected_num[rx] += connected_num[ry]

    # c++ set
    # https://nagiss.hateblo.jp/entry/2020/09/08/203701
    
    class SegTree:
        """
        ref: https://qiita.com/takayg1/items/c811bd07c21923d7ec69
        init(init_val, ide_ele): 配列init_valで初期化 O(N)
        update(k, x): k番目の値をxに更新 O(logN)
        query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
        """
        def __init__(self, init_val, segfunc, ide_ele):
            """
            init_val: 配列の初期値
            segfunc: 区間にしたい操作
            ide_ele: 単位元
            n: 要素数
            num: n以上の最小の2のべき乗
            tree: セグメント木(1-index)
            """
            n = len(init_val)
            self.segfunc = segfunc
            self.ide_ele = ide_ele
            self.num = 1 << (n - 1).bit_length()
            self.tree = [ide_ele] * 2 * self.num
            # 配列の値を葉にセット
            for i in range(n):
                self.tree[self.num + i] = init_val[i]
            # 構築していく
            for i in range(self.num - 1, 0, -1):
                self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

        def update(self, k, x):
            """
            k番目の値をxに更新
            k: index(0-index)
            x: update value
            """
            k += self.num
            self.tree[k] = x
            while k > 1:
                self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
                k >>= 1

        def query(self, l, r):
            """
            [l, r)のsegfuncしたものを得る
            l: index(0-index)
            r: index(0-index)
            """
            res = self.ide_ele
            l += self.num
            r += self.num
            while l < r:
                if l & 1:
                    res = self.segfunc(res, self.tree[l])
                    l += 1
                if r & 1:
                    res = self.segfunc(res, self.tree[r - 1])
                l >>= 1
                r >>= 1
            return res

    # ************ Graph ************
    # Graph: https://en.wikipedia.org/wiki/Directed_graph
    # 最短経路問題: https://ja.wikipedia.org/wiki/%E6%9C%80%E7%9F%AD%E7%B5%8C%E8%B7%AF%E5%95%8F%E9%A1%8C
    
    # Bellman-Ford: O(|V||E|). Use this if there exists an edge with negative length in the graph
    # After N steps, the shortest path has converded if there doesn't exist an cycle of edges with negative
    # Watch out: d[N] == d[2*N] doesn't necessarily mean the graph doesn't have negative cycle
    # ref: https://www.youtube.com/watch?v=1Z6ofKN03_Y

    def BellmanFord(N, M, ABC, vertex_start, vertex_end, value_if_inf = -1, find_shortest = False):
        """to calculate furthest or shortest length between vertex_start and vertex_end using BellmanFord algorithm
        
        Args:
            N (int): number of vertices
            M (int): number of edges
            ABC (list): [(ai, bi, ci) for _ in range(N)] where i-th edge is directed from vertex ai to vertex bi and the length is ci 
            vertex_start (int): start vertex. usually use 0.
            vertex_end (int): end vertex. usually use N-1.
            value_if_inf (int or string as you like, optional): value you want when the furthest (or shortest) distance is infinite (or -infinite). Defaults to -1.
            find_shortest (bool, optional): choose False to find furthest path. Defaults to False.
        
        Returns:
            int or string: normally int (but can be str if you set value_if_inf to str)
            
        Example:
                N, M, P = R()
                ABC = [R() for _ in range(M)]
                ABC = [(a-1, b-1, c-P) for a, b, c in ABC]
                print(BellmanFord(N, M, ABC, 0, N-1, value_if_inf = 'inf'))

        """

        def make_reachable_list(N, M, ABC, vertex_start, vertex_end):
            reachable_to_direct = defaultdict(list)
            reachable_from_direct = defaultdict(list)
            reachable_from_start = [False] * N
            reachable_to_end = [False] * N
            reachable_from_start[vertex_start] = True
            reachable_to_end[vertex_end] = True
            reachable_from_both_sides = [False] * N
            dfs_from_start = []
            dfs_to_end = []
            for a, b, c in ABC:
                reachable_to_direct[a].append(b)
                reachable_from_direct[b].append(a)
                if a == vertex_start:
                    dfs_from_start.append(b)
                    reachable_from_start[b] = True
                if b == vertex_end:
                    dfs_to_end.append(a)
                    reachable_to_end[a] = True
            while dfs_from_start:
                v = dfs_from_start.pop()
                for i in reachable_to_direct[v]:
                    if not reachable_from_start[i]:
                        reachable_from_start[i] = True
                        dfs_from_start.append(i)
            while dfs_to_end:
                v = dfs_to_end.pop()
                for i in reachable_from_direct[v]:
                    if not reachable_to_end[i]:
                        reachable_to_end[i] = True
                        dfs_to_end.append(i)
            for i in range(N):
                reachable_from_both_sides[i] = reachable_from_start[i] and reachable_to_end[i]
            return reachable_from_both_sides
        
        reachable_from_both_sides = make_reachable_list(N, M, ABC, vertex_start, vertex_end)
        
        if find_shortest:
            dist = [INF for i in range(N)]
        else:
            dist = [-INF for i in range(N)]
        
        dist[vertex_start] = 0
        for i in range(N):
            updated = False
            for a, b, c in ABC:
                if not reachable_from_both_sides[a]:
                    continue
                elif find_shortest:
                    update_condition = dist[a] + c < dist[b]
                else:
                    update_condition = dist[a] + c > dist[b]
                if dist[a] != INF and update_condition:
                    dist[b] = dist[a] + c
                    updated = True
                    if i == N-1:
                        return value_if_inf
            if not updated:
                break
        return dist[vertex_end]

    # Warshall Floyd O(V**3)
    def warshall_floyd(number_vertex, XYD, shift_one_for_vertex=False):
        # ref: https://juppy.hatenablog.com/entry/2018/11/01/%E8%9F%BB%E6%9C%AC_python_%E5%85%A8%E7%82%B9%E5%AF%BE%E6%9C%80%E7%9F%AD%E7%B5%8C%E8%B7%AF%E6%B3%95%EF%BC%88%E3%83%AF%E3%83%BC%E3%82%B7%E3%83%A3%E3%83%AB%E3%83%95%E3%83%AD%E3%82%A4%E3%83%89%E6%B3%95
        # number_vertex: len(vertex)
        # XYD: list of distance from x to y
        # shift_one_for_vertex: XYDの値が1~Nの時(0~N-1でない時)に調整するフラグ。
        # d[i][j]: iからjへの最短距離
        d = [[float("inf")]*number_vertex for i in range(number_vertex)]
        for x, y, dist in XYD:
            if shift_one_for_vertex:
                x = x - 1
                y = y - 1
            d[x][y] = dist
            d[y][x] = dist
        for i in range(number_vertex):
            d[i][i] = 0 # distance of same vertex is 0
        for k in range(number_vertex):
            for i in range(number_vertex):
                for j in range(number_vertex):
                    d[i][j] = min(d[i][j],d[i][k] + d[k][j])
        return d


    """ initialize variables and set inputs
    # initialize variables
        # to initialize list, use [0] * n
        # to initialize two dimentional array:
            # ex) [[0] * N for _ in range(N)]
            # ex2) dp = [[0] * (N+1) for _ in range(W*2)]
    # set inputs
        # put inputs between specific values (almost as quickly)
        # ex) S = [-INF] + [int(r()) for _ in range(A)] + [INF]
        # open(0).read() is sometimes useful:
        # ex) n, m, *x = map(int, open(0).read().split())
        #     min(x[::2]) - max(x[1::2])
        # ex2) *x, = map(int, open(0).read().split())
        #     don't forget to add comma after *x if only one variable is used
    # preprocessing
        # transpose = [x for x in zip(*data)]
        # ex) [[1, 2, 3], [4, 5, 6], [7, 8, 9]] => [(1, 4, 7), (2, 5, 8), (3, 6, 9)]
        # flat = [flatten for inner in data for flatten in inner]
        # ex) [[1, 2, 3], [4, 5, 6], [7, 8, 9]] => [1, 2, 3, 4, 5, 6, 7, 8, 9]
    # calculate and output
        # output pattern
        # ex1) print(*l) => when l = [2, 5, 6], printed 2 5 6
    """

    # functions to read input
    r = lambda: sys.stdin.readline().strip()
    r_int = lambda: int(r())
    r_float = lambda: float(r())
    R = lambda: list(map(int, r().split()))
    R_str = lambda: r().split()
    R_map = lambda: map(int, r().split())
    R_float = lambda: list(map(float, r().split()))
    R_tuple = lambda: tuple(map(int, r().split()))

    """ how to treat input
    # single int: int(r())
    # single string: r()
    # single float: float(r())
    # line int: R()
    # line string: r().split()
    # line (str, int, int): [j if i == 0 else int(j) for i, j in enumerate(r().split())]
    # lines int: [R() for _ in range(n)]
    """

    # for test
    if sample_file:
        sys.stdin = open(sample_file)
        
    # ----------------------------------
    # main
    #%%

    # H, W, K = R()
    # C = [R_str() for _ in range(H)]
    # D = []
    # ans = 0
    
    # for i in range(2**H):
    #     for j in range(2**W):
    #         C_ = C.copy()
    #         bin_h = format(i, '08b')
    #         bin_w = format(j, '08b')
    #         for k in range(H):
    #             if bin_h[-k-1] == "1":
    #                 for l in range(W):
    #                     C_[k][l] = "."
    #         for k in range(W):
    #             if bin_w[-k-1] == "1":
    #                 for l in range(H):
    #                     C_[l][k] = "."
    #         cnt = 0
    #         for i in range(H):
    #             for j in range(W):
    #                 if C_[i][j] == "#":
    #                     cnt += 1
    #         if cnt == K:
    #             ans += 1
    # print(ans)

    S = r_int()
    dp = [0]*(S+1)
    dp[0] = 1
    tmp = 0
        
    for i in range(3, S+1):
        tmp = (tmp + dp[i-3])%(10**9+7)
        dp[i] = tmp
    
    print(dp[S])
    

    # D = r_int()
    # C = R()
    # S = [R() for _ in range(D)]
    # # T = [r_int() for _ in range(D)]
    
    # def calc_score(D, C, S, T):
    #     sat = 0
    #     satl = [0] * D
    #     DI = [0] * 26 # daily irritation
    #     T_ = [t-1 for t in T]
    #     for i, t in enumerate(T_):
    #         for j in range(26):
    #             if j != t:
    #                 DI[j] += 1
    #                 sat -= C[j] * DI[j]
    #             else: # j == t
    #                 DI[j] = 0
    #                 sat += S[i][j]
    #         satl[i] = sat
    #     # return satl
    #     return sat
    
    # def donyoku(D, C, S):
    #     # return T
    #     DI = [0] * 26
    #     T = [0] * D
    #     for i in range(D):
    #         candidate = -1
    #         candidate_value = -INF
    #         for j in range(26):
    #             tmp_j = (DI[j] + 1) * C[j] + S[i][j] # merit
    #             if candidate_value < tmp_j:
    #                 candidate_value = tmp_j
    #                 candidate = j
    #         T[i] = candidate
    #     return [t+1 for t in T]

    # def emphasize_c(D, C, S, emp = 0.9):
    #     # return T
    #     DI = [0] * 26
    #     T = [0] * D
    #     for i in range(D):
    #         candidate = -1
    #         candidate_value = -INF
    #         for j in range(26):
    #             tmp_j = (DI[j] + 1) * C[j] + S[i][j] * emp # merit
    #             if candidate_value < tmp_j:
    #                 candidate_value = tmp_j
    #                 candidate = j
    #         T[i] = candidate
    #     return [t+1 for t in T]

    # def update_one(T, score):
    #     target_t = random.randint(0, D-1)
    #     after_abc = random.randint(1, 24)
    #     before_abc = T[target_t]
    #     T[target_t] = after_abc
    #     tmp = calc_score(D, C, S, T)
    #     if score < tmp:
    #         score = tmp
    #     else:
    #         T[target_t] = before_abc
    #     return T, score
    
    # def change_two(T, score):
    #     target_1, target_2 = random.sample(range(0, D), 2)
    #     before_1 = T[target_1]
    #     before_2 = T[target_2]
    #     T[target_1] = before_2
    #     T[target_2] = before_1
    #     tmp = calc_score(D, C, S, T)
    #     if score < tmp:
    #         score = tmp
    #     else:
    #         T[target_1] = before_1
    #         T[target_2] = before_2
    #     return T, score

    # import time
    # start = time.perf_counter()
    
    # T = [1] * D
    # score = -INF
    # Cand = [donyoku(D, C, S), emphasize_c(D, C, S), emphasize_c(D, C, S, 0.5), emphasize_c(D, C, S, 0)]
    # for c in Cand:
    #     tmp = calc_score(D, C, S, c)
    #     if tmp > score:
    #         T = c
    #         score = tmp
    
    # import random
    # while time.perf_counter() - start < 1.8:
    #     if random.random() < 0.5:
    #         T, score = update_one(T, score)
    #     else:
    #         T, score = change_two(T, score)

    # print(*T, sep='\n')


    #%%
    # end of main
    # ----------------------------------

    """memo: how to use defaultdict of list
    # initialize
    Dic = defaultdict(list)
    # append / extend
    Dic[x].append(y)
    # three methods for loop: keys(), values(), items()
    for k, v in Dic.items():
    """
    
    """memo: how to solve binary problems
    # to make binary digits text
    >>> a = 5
    >>> bin_str_a = format(a, '#06b')
    >>> print(bin_str_a)
    0b0101 # first 2 strings (='0b') indicates it is binary
    """
    
    """memo: how to solve the problem
    creating simple test/answer
    greed
    simple dp
    graph
    """

if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
def main(sample_file = ''):

    """ convenient functions
    # for i, a in enumerate(iterable)
    # q, mod = divmod(a, b)
    # divmod(x, y) returns the tuple (x//y, x%y)
    # Higher-order function: reduce(operator.mul, xyz_count, 1)
    # manage median(s) using two heapq https://atcoder.jp/contests/abc127/tasks/abc127_f
    """

    """convenient decorator
    # @functools.lru_cache():
    # to facilitate use of recursive function
        # ex:
        # from functools import lru_cache
        # import sys
        # sys.setrecursionlimit(10**9)
        # @lru_cache(maxsize=None)
        # def fib(n):
        #     if n < 2:
        #         return n
        #     return fib(n-1) + fib(n-2)
        # print(fib(1000))
    """
    
    # import numpy as np
    import sys
    sys.setrecursionlimit(10**7)
    from itertools import accumulate, combinations, permutations, product, combinations_with_replacement # https://docs.python.org/ja/3/library/itertools.html
    # accumulate() returns iterator! to get list: list(accumulate())
    from math import factorial, ceil, floor, sqrt
    def factorize(n):
        """return the factors of the Arg and count of each factor
        
        Args:
            n (long): number to be resolved into factors
        
        Returns:
            list of tuples: factorize(220) returns [(2, 2), (5, 1), (11, 1)]
        """
        fct = []  # prime factor
        b, e = 2, 0  # base, exponent
        while b * b <= n:
            while n % b == 0:
                n = n // b
                e = e + 1
            if e > 0:
                fct.append((b, e))
            b, e = b + 1, 0
        if n > 1:
            fct.append((n, 1))
        return fct
    def combinations_count(n, r):   
        """Return the number of selecting r pieces of items from n kinds of items.
        
        Args:
            n (long): number
            r (long): number
        
        Raises:
            Exception: not defined when n or r is negative
        
        Returns:
            long: number
        """
        # TODO: How should I do when n - r is negative?
        if n < 0 or r < 0:
            raise Exception('combinations_count(n, r) not defined when n or r is negative')
        if n - r < r: r = n - r
        if r < 0: return 0
        if r == 0: return 1
        if r == 1: return n
        numerator = [n - r + k + 1 for k in range(r)]
        denominator = [k + 1 for k in range(r)]
        for p in range(2,r+1):
            pivot = denominator[p - 1]
            if pivot > 1:
                offset = (n - r) % p
                for k in range(p-1,r,p):
                    numerator[k - offset] /= pivot
                    denominator[k] /= pivot
        result = 1
        for k in range(r):
            if numerator[k] > 1:
                result *= int(numerator[k])
        return result
    def combinations_with_replacement_count(n, r):
        """Return the number of selecting r pieces of items from n kinds of items allowing individual elements to be repeated more than once.
        
        Args:
            n (long): number
            r (long): number
        
        Raises:
            Exception: not defined when n or r is negative
        
        Returns:
            long: number
        """
        if n < 0 or r < 0:
            raise Exception('combinations_with_replacement_count(n, r) not defined when n or r is negative')
        elif n == 0:
            return 1
        else:
            return combinations_count(n + r - 1, r)
    from bisect import bisect_left, bisect_right
    from collections import deque, Counter, defaultdict # https://docs.python.org/ja/3/library/collections.html#collections.deque
    from heapq import heapify, heappop, heappush, heappushpop, heapreplace,nlargest,nsmallest # https://docs.python.org/ja/3/library/heapq.html
    from copy import deepcopy, copy # https://docs.python.org/ja/3/library/copy.html
    import operator
    from operator import itemgetter #sort 
    # ex1: List.sort(key=itemgetter(1))
    # ex2: sorted(tuples, key=itemgetter(1,2))
    from functools import reduce, lru_cache
    def chmin(x, y):
        """change minimum
        if x > y, x = y and return (x, True).
        convenient when solving problems of dp[i]
        
        Args:
            x (long): current minimum value
            y (long): potential minimum value
        
        Returns:
            (x, bool): (x, True) when updated, else (x, False)
        """
        if x > y:
            x = y
            return (x, True)
        else:
            return (x, False)
    def chmax(x, y):
        """change maximum
        if x < y, x = y and return (x, True).
        convenient when solving problems of dp[i]
        
        Args:
            x (long): current maximum value
            y (long): potential maximum value
        
        Returns:
            (x, bool): (x, True) when updated, else (x, False)
        """
        if x < y:
            x = y
            return (x, True)
        else:
            return (x, False)

    from fractions import gcd
    def gcd(a,b):
        # from fractions import gcd # Deprecated since version 3.5: Use math.gcd() instead.
        # => 最近の環境でfractions.gcdを使うとTLEする。
        if a<b:
            a, b = b, a
        while a%b !=0 :
            a, b = b, a%b
        return b

    # def gcd(p,q):
    #     while q != 0:
    #         r = p % q
    #         p = q
    #         q = r
    #     return p

    def gcds(numbers):
        return reduce(gcd, numbers)
    def lcm(x, y):
        return (x * y) // gcd(x, y)
    def lcms(numbers):
        return reduce(lcm, numbers, 1)
    def make_divisors(n, reversed=False):
        """create list of divisors
        
        Args:
            number (int): number from which list of divisors is created
            reversed (bool, optional): ascending order if False. Defaults to False.
        
        Returns:
            list: list of divisors
        """
        divisors = set()
        for i in range(1, int(n**0.5)+1):
            if n % i == 0:
                divisors.add(i)
                divisors.add(n//i)
        return sorted(list(divisors),reverse=reversed)

    # Eratosthenesの篩により、整数end未満の素数を列挙する
    def sieve_of_eratosthenes(end, typecode="L"):
        # len(sieve_of_eratosthenes(10**7)) => 664579; 514ms in pypy
        # len(sieve_of_eratosthenes(10**6)) => 78498; 134ms in pypy

        # https://hamukichi.hatenablog.jp/entry/2016/02/17/215948#Eratosthenes%E3%81%AE%E7%AF%A9%E3%81%A8%E5%8C%BA%E9%96%93%E7%AF%A9
        import array
        import textwrap
        assert end > 1
        # 整数iが素数であるかをis_prime[i]が示す
        # 最初はすべてTrueで初期化しておく
        # 最終的にprimesではなくこれを返してもよい
        is_prime = array.array("B", (True for i in range(end)))
        # 0, 1はいずれも素数ではない
        is_prime[0] = False
        is_prime[1] = False
        # 素数を格納する配列
        primes = array.array(typecode)
        # 篩う
        for i in range(2, end):
            if is_prime[i]:
                primes.append(i)
                for j in range(2 * i, end, i):
                    is_prime[j] = False  # 素数ではないため除外する
        return primes

    class PrimeFactorization:
        '''初期化にO(NloglogN)/ 因数分解クエリをO(log(k))/ 素数判定クエリをO(1)
        >>> pf = PrimeFactorization(100)
        >>> pf.query(100)
        ((2, 2), (5, 2))
        
        '''
        # 自分で実装した。
        # https://atcoder.jp/contests/abc177/editorial/82
        # 高速素因数分解
        # 問題： A 以下の数が N 個与えられる。全て素因数分解せよ。
        # 前計算としてエラトステネスの篩を行い、「その数をふるい落とした素数」を配列 D に記録します。
        # 例えば D[4]=D[6]=2,D[35]=5 です。x が素数のときは D[x]=x としておきます。この配列はエラトステネスの篩と同様 O(AloglogA) で構築できます。
        # D[x] は x を割り切る最小の素数なので、この配列 D を利用すると素因数分解を行うときに「試し割り」をする必要がなくなり(D[x]で割ればよい)、1つの数の素因数分解が素因数の個数である O(logA) でできるようになります。
        def __init__(self, Num=10**6):
            from collections import defaultdict
            from math import floor
            self.Num = Num
            self.D = [-1] * (Num+1)
            for i in range(2, Num+1):
                if self.D[i] != -1:
                    continue
                self.D[i] = i
                for j in range(1, floor(Num/i)+1):
                    if self.D[j*i] != -1:
                        continue
                    else:
                        self.D[j*i] = i
        
        def query(self, k):
            ans = defaultdict(int)
            tmp = k
            while self.D[tmp] != -1:
                div = self.D[tmp]
                ans[div] += 1
                tmp = tmp//div
            return tuple(ans.items())
        
        def is_prime(self, k):
            return k == self.D[k]

    # first create factorial_list
    # fac_list = modfactorial_list(n)
    INF = 10 ** 18
    MOD = 10 ** 9 + 7
    AtoZ = list('abcdefghijklmnopqrsruvwxyz') # 26
    modpow = lambda a, n, p = MOD: pow(a, n, p) # Recursive function in python is slow!
    def modinv(a, p = MOD):
        # evaluate reciprocal using Fermat's little theorem:
        # a**(p-1) is identical to 1 (mod p) when a and p is coprime
        return modpow(a, p-2, p)
    def modinv_list(n, p = MOD):
        if n <= 1:
            return [0,1][:n+1]
        else:
            inv_t = [0,1]
            for i in range(2, n+1):
                inv_t += [inv_t[p % i] * (p - int(p / i)) % p]
            return inv_t
    def modfactorial_list(n, p = MOD):
        if n == 0:
            return [1]
        else:
            l = [0] * (n+1)
            tmp = 1
            for i in range(1, n+1):
                tmp = tmp * i % p
                l[i] = tmp
            return l
    def modcomb(n, k, fac_list = [], p = MOD):
        # fac_list = modfactorial_list(100)
        # print(modcomb(100, 5, modfactorial_list(100)))
        from math import factorial
        if n < 0 or k < 0 or n < k: return 0
        if n == 0 or k == 0: return 1
        if len(fac_list) <= n:
            a = factorial(n) % p
            b = factorial(k) % p
            c = factorial(n-k) % p
        else:
            a = fac_list[n]
            b = fac_list[k]
            c = fac_list[n-k]
        return (a * modpow(b, p-2, p) * modpow(c, p-2, p)) % p
    def modadd(a, b, p = MOD):
        return (a + b) % MOD
    def modsub(a, b, p = MOD):
        return (a - b) % p
    def modmul(a, b, p = MOD):
        return ((a % p) * (b % p)) % p
    def moddiv(a, b, p = MOD):
        return modmul(a, modpow(b, p-2, p))

    class UnionFindTree:
        """union find tree class
        TODO: fix this description...
        how to use (example):
        >>  uf = UnionFindTree(N) 
        >>  if uf.find_root(a) == uf.find_root(b):
        >>      do something like:
        >>      pass
        >>  else:
        >>      do something like:
        >>      L[find_root(a)] = L[find_root(a)] + L[find_root(b)]
        >>      L[find_root(b)] = L[find_root(a)]
        >>      
        >>      uf.unite(a, b)
        """
        def __init__(self, N):
            self.root = [-1] * (N+1)
            self.rank   = [0]  * (N+1)
            self.connected_num = [1] * (N+1)
    
        def find_root(self,x):
            root = self.root
            while root[x] != -1:
                x = root[x]
            return x
    
        def unite(self,x,y):
            root = self.root
            rank = self.rank
            connected_num = self.connected_num
            find_root = self.find_root
    
            rx = find_root(x)
            ry = find_root(y)
            if rx != ry:
                if rank[rx] < rank[ry]:
                    root[rx] = ry
                    rx,ry = ry,rx
                else:
                    if rank[rx] == rank[ry]:
                        rank[rx] += 1
                    root[ry] = rx       
                connected_num[rx] += connected_num[ry]

    # c++ set
    # https://nagiss.hateblo.jp/entry/2020/09/08/203701
    
    class SegTree:
        """
        ref: https://qiita.com/takayg1/items/c811bd07c21923d7ec69
        init(init_val, ide_ele): 配列init_valで初期化 O(N)
        update(k, x): k番目の値をxに更新 O(logN)
        query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
        """
        def __init__(self, init_val, segfunc, ide_ele):
            """
            init_val: 配列の初期値
            segfunc: 区間にしたい操作
            ide_ele: 単位元
            n: 要素数
            num: n以上の最小の2のべき乗
            tree: セグメント木(1-index)
            """
            n = len(init_val)
            self.segfunc = segfunc
            self.ide_ele = ide_ele
            self.num = 1 << (n - 1).bit_length()
            self.tree = [ide_ele] * 2 * self.num
            # 配列の値を葉にセット
            for i in range(n):
                self.tree[self.num + i] = init_val[i]
            # 構築していく
            for i in range(self.num - 1, 0, -1):
                self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

        def update(self, k, x):
            """
            k番目の値をxに更新
            k: index(0-index)
            x: update value
            """
            k += self.num
            self.tree[k] = x
            while k > 1:
                self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
                k >>= 1

        def query(self, l, r):
            """
            [l, r)のsegfuncしたものを得る
            l: index(0-index)
            r: index(0-index)
            """
            res = self.ide_ele
            l += self.num
            r += self.num
            while l < r:
                if l & 1:
                    res = self.segfunc(res, self.tree[l])
                    l += 1
                if r & 1:
                    res = self.segfunc(res, self.tree[r - 1])
                l >>= 1
                r >>= 1
            return res

    # ************ Graph ************
    # Graph: https://en.wikipedia.org/wiki/Directed_graph
    # 最短経路問題: https://ja.wikipedia.org/wiki/%E6%9C%80%E7%9F%AD%E7%B5%8C%E8%B7%AF%E5%95%8F%E9%A1%8C
    
    # Bellman-Ford: O(|V||E|). Use this if there exists an edge with negative length in the graph
    # After N steps, the shortest path has converded if there doesn't exist an cycle of edges with negative
    # Watch out: d[N] == d[2*N] doesn't necessarily mean the graph doesn't have negative cycle
    # ref: https://www.youtube.com/watch?v=1Z6ofKN03_Y

    def BellmanFord(N, M, ABC, vertex_start, vertex_end, value_if_inf = -1, find_shortest = False):
        """to calculate furthest or shortest length between vertex_start and vertex_end using BellmanFord algorithm
        
        Args:
            N (int): number of vertices
            M (int): number of edges
            ABC (list): [(ai, bi, ci) for _ in range(N)] where i-th edge is directed from vertex ai to vertex bi and the length is ci 
            vertex_start (int): start vertex. usually use 0.
            vertex_end (int): end vertex. usually use N-1.
            value_if_inf (int or string as you like, optional): value you want when the furthest (or shortest) distance is infinite (or -infinite). Defaults to -1.
            find_shortest (bool, optional): choose False to find furthest path. Defaults to False.
        
        Returns:
            int or string: normally int (but can be str if you set value_if_inf to str)
            
        Example:
                N, M, P = R()
                ABC = [R() for _ in range(M)]
                ABC = [(a-1, b-1, c-P) for a, b, c in ABC]
                print(BellmanFord(N, M, ABC, 0, N-1, value_if_inf = 'inf'))

        """

        def make_reachable_list(N, M, ABC, vertex_start, vertex_end):
            reachable_to_direct = defaultdict(list)
            reachable_from_direct = defaultdict(list)
            reachable_from_start = [False] * N
            reachable_to_end = [False] * N
            reachable_from_start[vertex_start] = True
            reachable_to_end[vertex_end] = True
            reachable_from_both_sides = [False] * N
            dfs_from_start = []
            dfs_to_end = []
            for a, b, c in ABC:
                reachable_to_direct[a].append(b)
                reachable_from_direct[b].append(a)
                if a == vertex_start:
                    dfs_from_start.append(b)
                    reachable_from_start[b] = True
                if b == vertex_end:
                    dfs_to_end.append(a)
                    reachable_to_end[a] = True
            while dfs_from_start:
                v = dfs_from_start.pop()
                for i in reachable_to_direct[v]:
                    if not reachable_from_start[i]:
                        reachable_from_start[i] = True
                        dfs_from_start.append(i)
            while dfs_to_end:
                v = dfs_to_end.pop()
                for i in reachable_from_direct[v]:
                    if not reachable_to_end[i]:
                        reachable_to_end[i] = True
                        dfs_to_end.append(i)
            for i in range(N):
                reachable_from_both_sides[i] = reachable_from_start[i] and reachable_to_end[i]
            return reachable_from_both_sides
        
        reachable_from_both_sides = make_reachable_list(N, M, ABC, vertex_start, vertex_end)
        
        if find_shortest:
            dist = [INF for i in range(N)]
        else:
            dist = [-INF for i in range(N)]
        
        dist[vertex_start] = 0
        for i in range(N):
            updated = False
            for a, b, c in ABC:
                if not reachable_from_both_sides[a]:
                    continue
                elif find_shortest:
                    update_condition = dist[a] + c < dist[b]
                else:
                    update_condition = dist[a] + c > dist[b]
                if dist[a] != INF and update_condition:
                    dist[b] = dist[a] + c
                    updated = True
                    if i == N-1:
                        return value_if_inf
            if not updated:
                break
        return dist[vertex_end]

    # Warshall Floyd O(V**3)
    def warshall_floyd(number_vertex, XYD, shift_one_for_vertex=False):
        # ref: https://juppy.hatenablog.com/entry/2018/11/01/%E8%9F%BB%E6%9C%AC_python_%E5%85%A8%E7%82%B9%E5%AF%BE%E6%9C%80%E7%9F%AD%E7%B5%8C%E8%B7%AF%E6%B3%95%EF%BC%88%E3%83%AF%E3%83%BC%E3%82%B7%E3%83%A3%E3%83%AB%E3%83%95%E3%83%AD%E3%82%A4%E3%83%89%E6%B3%95
        # number_vertex: len(vertex)
        # XYD: list of distance from x to y
        # shift_one_for_vertex: XYDの値が1~Nの時(0~N-1でない時)に調整するフラグ。
        # d[i][j]: iからjへの最短距離
        d = [[float("inf")]*number_vertex for i in range(number_vertex)]
        for x, y, dist in XYD:
            if shift_one_for_vertex:
                x = x - 1
                y = y - 1
            d[x][y] = dist
            d[y][x] = dist
        for i in range(number_vertex):
            d[i][i] = 0 # distance of same vertex is 0
        for k in range(number_vertex):
            for i in range(number_vertex):
                for j in range(number_vertex):
                    d[i][j] = min(d[i][j],d[i][k] + d[k][j])
        return d


    """ initialize variables and set inputs
    # initialize variables
        # to initialize list, use [0] * n
        # to initialize two dimentional array:
            # ex) [[0] * N for _ in range(N)]
            # ex2) dp = [[0] * (N+1) for _ in range(W*2)]
    # set inputs
        # put inputs between specific values (almost as quickly)
        # ex) S = [-INF] + [int(r()) for _ in range(A)] + [INF]
        # open(0).read() is sometimes useful:
        # ex) n, m, *x = map(int, open(0).read().split())
        #     min(x[::2]) - max(x[1::2])
        # ex2) *x, = map(int, open(0).read().split())
        #     don't forget to add comma after *x if only one variable is used
    # preprocessing
        # transpose = [x for x in zip(*data)]
        # ex) [[1, 2, 3], [4, 5, 6], [7, 8, 9]] => [(1, 4, 7), (2, 5, 8), (3, 6, 9)]
        # flat = [flatten for inner in data for flatten in inner]
        # ex) [[1, 2, 3], [4, 5, 6], [7, 8, 9]] => [1, 2, 3, 4, 5, 6, 7, 8, 9]
    # calculate and output
        # output pattern
        # ex1) print(*l) => when l = [2, 5, 6], printed 2 5 6
    """

    # functions to read input
    r = lambda: sys.stdin.readline().strip()
    r_int = lambda: int(r())
    r_float = lambda: float(r())
    R = lambda: list(map(int, r().split()))
    R_str = lambda: r().split()
    R_map = lambda: map(int, r().split())
    R_float = lambda: list(map(float, r().split()))
    R_tuple = lambda: tuple(map(int, r().split()))

    """ how to treat input
    # single int: int(r())
    # single string: r()
    # single float: float(r())
    # line int: R()
    # line string: r().split()
    # line (str, int, int): [j if i == 0 else int(j) for i, j in enumerate(r().split())]
    # lines int: [R() for _ in range(n)]
    """

    # for test
    if sample_file:
        sys.stdin = open(sample_file)
        
    # ----------------------------------
    # main
    #%%

    # H, W, K = R()
    # C = [R_str() for _ in range(H)]
    # D = []
    # ans = 0
    
    # for i in range(2**H):
    #     for j in range(2**W):
    #         C_ = C.copy()
    #         bin_h = format(i, '08b')
    #         bin_w = format(j, '08b')
    #         for k in range(H):
    #             if bin_h[-k-1] == "1":
    #                 for l in range(W):
    #                     C_[k][l] = "."
    #         for k in range(W):
    #             if bin_w[-k-1] == "1":
    #                 for l in range(H):
    #                     C_[l][k] = "."
    #         cnt = 0
    #         for i in range(H):
    #             for j in range(W):
    #                 if C_[i][j] == "#":
    #                     cnt += 1
    #         if cnt == K:
    #             ans += 1
    # print(ans)

    S = r_int()

    # print([1,2,3][2])
    print([1, 0, 0, 1, 1, 1, 2, 3, 4, 6, 9, 13, 19, 28, 41, 60, 88, 129, 189, 277, 406, 595, 872, 1278, 1873, 2745, 4023, 5896, 8641, 12664, 18560, 27201, 39865, 58425, 85626, 125491, 183916, 269542, 395033, 578949, 848491, 1243524, 1822473, 2670964, 3914488, 5736961, 8407925, 12322413, 18059374, 26467299, 38789712, 56849086, 83316385, 122106097, 178955183, 262271568, 384377665, 563332848, 825604416, 209982074, 773314922, 598919331, 808901405, 582216320, 181135644, 990037049, 572253362, 753389006, 743426048, 315679403, 69068402, 812494450, 128173846, 197242248, 9736691, 137910537, 335152785, 344889476, 482800013, 817952798, 162842267, 645642280, 463595071, 626437338, 272079611, 735674682, 362112013, 634191624, 369866299, 731978312, 366169929, 736036228, 468014533, 834184462, 570220683, 38235209, 872419671, 442640347, 480875556, 353295220, 795935567, 276811116, 630106336, 426041896, 702853012, 332959341, 759001237, 461854242, 794813583, 553814813, 15669048, 810482631, 364297437, 379966485, 190449109, 554746546, 934713031, 125162133, 679908679, 614621703, 739783836, 419692508, 34314204, 774098040, 193790541, 228104745, 2202778, 195993319, 424098064, 426300842, 622294161, 46392218, 472693060, 94987214, 141379432, 614072492, 709059706, 850439138, 464511623, 173571322, 24010453, 488522076, 662093398, 686103851, 174625920, 836719318, 522823162, 697449082, 534168393, 56991548, 754440630, 288609016, 345600564, 100041187, 388650203, 734250767, 834291954, 222942150, 957192917, 791484864, 14427007, 971619924, 763104781, 777531788, 749151705, 512256479, 289788260, 38939958, 551196437, 840984697, 879924655, 431121085, 272105775, 152030423, 583151508, 855257283, 7287699, 590439207, 445696483, 452984182, 43423382, 489119865, 942104047, 985527429, 474647287, 416751327, 402278749, 876926036, 293677356, 695956105, 572882134, 866559490, 562515588, 135397715, 1957198, 564472786, 699870501, 701827699, 266300478, 966170979, 667998671, 934299149, 900470121, 568468785, 502767927, 403238041, 971706826, 474474746, 877712787, 849419606, 323894345, 201607125, 51026724, 374921069, 576528194, 627554918, 2475980, 579004174, 206559085, 209035065, 788039239, 994598324, 203633382, 991672621, 986270938, 189904313, 181576927, 167847858, 357752171, 539329098, 707176956, 64929120, 604258218, 311435167, 376364287, 980622505, 292057665, 668421952, 649044450, 941102115, 609524060, 258568503, 199670611, 809194671, 67763167, 267433778, 76628442, 144391609, 411825387, 488453829, 632845438, 44670818, 533124647, 165970078, 210640896, 743765543, 909735621, 120376510, 864142053, 773877667, 894254177, 758396223, 532273883, 426528053, 184924269, 717198152, 143726198, 328650467, 45848612, 189574810, 518225277, 564073889, 753648699, 271873969, 835947858, 589596550, 861470519, 697418370, 287014913, 148485425, 845903795, 132918701, 281404126, 127307914, 260226615, 541630741, 668938655, 929165270, 470796004, 139734652, 68899915, 539695919, 679430571, 748330486, 288026398, 967456969, 715787448, 3813839, 971270808, 687058249, 690872088, 662142889, 349201131, 40073212, 702216101, 51417225, 91490437, 793706538, 845123763, 936614200, 730320731, 575444487, 512058680, 242379404, 817823891, 329882564, 572261968, 390085852, 719968416, 292230377, 682316229, 402284638, 694515015, 376831237, 779115875, 473630883, 850462120, 629577988, 103208864, 953670984, 583248965, 686457829, 640128806, 223377764, 909835593, 549964392, 773342156, 683177742, 233142127, 6484276, 689662018, 922804145, 929288421, 618950432, 541754570, 471042984, 89993409, 631747979, 102790956, 192784365, 824532344, 927323300, 120107658, 944640002, 871963295, 992070953, 936710948, 808674236, 800745182, 737456123, 546130352, 346875527, 84331643, 630461995, 977337522, 61669158, 692131153, 669468668, 731137826, 423268972, 92737633, 823875459, 247144424, 339882057, 163757509, 410901933, 750783990, 914541499, 325443425, 76227408, 990768907, 316212325, 392439733, 383208633, 699420958, 91860684, 475069317, 174490268, 266350952, 741420269, 915910537, 182261482, 923681751, 839592281, 21853756, 945535507, 785127781, 806981537, 752517037, 537644811, 344626341, 97143371, 634788182, 979414523, 76557887, 711346069, 690760585, 767318472, 478664534, 169425112, 936743584, 415408111, 584833223, 521576800, 936984911, 521818127, 43394920, 980379831, 502197951, 545592871, 525972695, 28170639, 573763510, 99736198, 127906837, 701670347, 801406545, 929313382, 630983722, 432390260, 361703635, 992687357, 425077610, 786781245, 779468595, 204546198, 991327443, 770796031, 975342229, 966669665, 737465689, 712807911, 679477569, 416943251, 129751155, 809228724, 226171968, 355923123, 165151840, 391323808, 747246931, 912398771, 303722572, 50969496, 963368267, 267090832, 318060328, 281428588, 548519420, 866579748, 148008329, 696527749, 563107490, 711115819, 407643561, 970751051, 681866863, 89510417, 60261461, 742128324, 831638741, 891900202, 634028519, 465667253, 357567448, 991595967, 457263213, 814830661, 806426621, 263689827, 78520481, 884947102, 148636922, 227157403, 112104498, 260741420, 487898823, 600003321, 860744741, 348643557, 948646878, 809391612, 158035162, 106682033, 916073645, 74108800, 180790833, 96864471, 170973271, 351764104, 448628575, 619601846, 971365950, 419994518, 39596357, 10962300, 430956818, 470553175, 481515475, 912472293, 383025461, 864540936, 777013222, 160038676, 24579605, 801592827, 961631503, 986211108, 787803928, 749435424, 735646525, 523450446, 272885863, 8532381, 531982827, 804868690, 813401071, 345383891, 150252574, 963653645, 309037529, 459290103, 422943741, 731981270, 191271366, 614215107, 346196370, 537467736, 151682836, 497879206, 35346935, 187029771, 684908977, 720255912, 907285683, 592194653, 312450558, 219736234, 811930887, 124381438, 344117672, 156048552, 280429990, 624547662, 780596214, 61026197, 685573859, 466170066, 527196263, 212770115, 678940181, 206136437, 418906552, 97846726, 303983163, 722889715, 820736441, 124719597, 847609312, 668345746, 793065343, 640674648, 309020387, 102085723, 742760371, 51780751, 153866474, 896626845, 948407596, 102274063, 998900908, 947308497, 49582553, 48483454, 995791951, 45374497, 93857951, 89649895, 135024392, 228882343, 318532238, 453556630, 682438973, 971204, 454527834, 136966800, 137938004, 592465838, 729432638, 867370642, 459836473, 189269104, 56639739, 516476212, 705745316, 762385055, 278861260, 984606576, 746991624, 25852877, 10459446, 757451070, 783303947, 793763393, 551214456, 334518396, 128281782, 679496238, 14014627, 142296409, 821792647, 835807274, 978103683, 799896323, 635703590, 613807266, 413703582, 49407165, 663214431, 76918006, 126325171, 789539602, 866457608, 992782779, 782322374, 648779975, 641562747, 423885114, 72665082, 714227829, 138112936, 210778018, 925005847, 63118776, 273896794, 198902634, 262021410, 535918204, 734820838, 996842248, 532760445, 267581276, 264423517, 797183962, 64765231, 329188748, 126372703, 191137934, 520326682, 646699385, 837837319, 358163994, 4863372, 842700691, 200864678, 205728050, 48428734, 249293412, 455021462, 503450196, 752743608, 207765063, 711215259, 463958860, 671723923, 382939175, 846898035, 518621951, 901561126, 748459154, 267081098, 168642217, 917101371, 184182462, 352824679, 269926043, 454108505, 806933184, 76859220, 530967725, 337900902, 414760122, 945727847, 283628742, 698388864, 644116704, 927745446, 626134303, 270251000, 197996439, 824130742, 94381735, 292378174, 116508909, 210890644, 503268818, 619777727, 830668371, 333937182, 953714909, 784383273, 118320448, 72035350, 856418623, 974739071, 46774414, 903193037, 877932101, 924706515, 827899545, 705831639, 630538147, 458437685, 164269317, 794807464, 253245142, 417514459, 212321916, 465567058, 883081517, 95403426, 560970484, 444051994, 539455420, 100425897, 544477891, 83933304, 184359201, 728837092, 812770396, 997129597, 725966682, 538737071, 535866661, 261833336, 800570407, 336437061, 598270397, 398840797, 735277858, 333548248, 732389045, 467666896, 801215144, 533604182, 1271071, 802486215, 336090390, 337361461, 139847669, 475938059, 813299520, 953147189, 429085241, 242384754, 195531936, 624617177, 867001931, 62533860, 687151037, 554152961, 616686821, 303837851, 857990812, 474677626, 778515477, 636506282, 111183901, 889699378, 526205653, 637389554, 527088925, 53294571, 690684125, 217773043, 271067614, 961751739, 179524775, 450592389, 412344121, 591868896, 42461278, 454805399, 46674288, 89135566, 543940965, 590615253, 679750819, 223691777, 814307030, 494057842, 717749619, 532056642, 26114477, 743864096, 275920731, 302035208, 45899297, 321820028, 623855236, 669754533, 991574561, 615429790, 285184316, 276758870, 892188660, 177372969, 454131839, 346320492, 523693461, 977825300, 324145785, 847839246, 825664539, 149810317, 997649563, 823314095, 973124412, 970773968, 794088056, 767212461, 737986422, 532074471, 299286925, 37273340, 569347811, 868634736, 905908076, 475255880, 343890609, 249798678, 725054558, 68945160, 318743838, 43798389, 112743549, 431487387, 475285776, 588029325, 19516705, 494802481, 82831799, 102348504, 597150985, 679982784, 782331288, 379482266, 59465043, 841796331, 221278590, 280743633, 122539957, 343818547, 624562180, 747102137, 90920677, 715482857, 462584987, 553505664, 268988514, 731573501, 285079158, 554067672, 285641166, 570720324, 124787989, 410429155, 981149479, 105937461, 516366616, 497516088, 603453549, 119820158, 617336246, 220789788, 340609946, 957946192, 178735973, 519345919, 477292104, 656028077, 175373989, 652666093, 308694163, 484068152, 136734238, 445428401, 929496553, 66230784, 511659185, 441155731, 507386515, 19045693, 460201424, 967587939, 986633632, 446835049, 414422981, 401056606, 847891655, 262314629, 663371235, 511262883, 773577512, 436948740, 948211623, 721789128, 158737861, 106949477, 828738605, 987476466, 94425936, 923164541, 910641000, 5066929, 928231470, 838872463, 843939392, 772170855, 611043311, 454982696, 227153544, 838196855, 293179544, 520333088, 358529936, 651709480, 172042561, 530572497, 182281970, 354324531, 884897028, 67178991, 421503522, 306400543, 373579534, 795083056, 101483592, 475063126, 270146175, 371629767, 846692893, 116839061, 488468828, 335161714, 452000775, 940469603, 275631310, 727632085, 668101681, 943732991, 671365069, 339466743, 283199727, 954564796, 294031532, 577231259, 531796048, 825827580, 403058832, 934854880, 760682453, 163741278, 98596151, 859278604, 23019875, 121616026, 980894630, 3914498, 125530524, 106425147, 110339645, 235870169, 342295316, 452634961, 688505130, 30800439, 483435400, 171940523, 202740962, 686176362, 858116885, 60857840, 747034202, 605151080, 666008920, 413043115, 18194188, 684203108, 97246216, 115440404, 799643512, 896889728, 12330125, 811973637, 708863358, 721193483, 533167113, 242030464, 963223947, 496391053, 738421517, 701645457, 198036503, 936458020, 638103470, 836139973, 772597986, 410701449, 246841415, 19439394, 430140843, 676982258, 696421652, 126562488, 803544746, 499966391, 626528879, 430073618, 930040009, 556568881, 986642499, 916682501, 473251375, 459893867, 376576361, 849827736, 309721596, 686297957, 536125686, 845847282, 532145232, 68270911, 914118193, 446263418, 514534329, 428652515, 874915933, 389450255, 818102770, 693018696, 82468944, 900571714, 593590403, 676059347, 576631054, 170221450, 846280797, 422911844, 593133294, 439414084, 862325928, 455459215, 894873299, 757199220, 212658428, 107531720, 864730940, 77389361, 184921081, 49652014, 127041375, 311962456, 361614470, 488655845, 800618301, 162232764, 650888609, 451506903, 613739667, 264628269, 716135172, 329874832, 594503101, 310638266, 640513098, 235016192, 545654458, 186167549, 421183741, 966838199, 153005741, 574189482, 541027674, 694033415, 268222890, 809250564, 503283972, 771506862, 580757419, 84041384, 855548246, 436305658, 520347042, 375895281, 812200939, 332547974, 708443255, 520644187, 853192161, 561635409, 82279589, 935471750, 497107152, 579386741, 514858484, 11965629, 591352370, 106210847, 118176476, 709528846, 815739693, 933916169, 643445008, 459184694, 393100856, 36545857, 495730551, 888831407, 925377264, 421107808, 309939208, 235316465, 656424273, 966363481, 201679939, 858104212, 824467686, 26147618, 884251830, 708719509, 734867127, 619118950, 327838452, 62705572, 681824522, 9662967, 72368539, 754193061, 763856028, 836224567, 590417621, 354273642, 190498202, 780915823, 135189458, 325687660, 106603476, 241792934, 567480594, 674084070, 915877004, 483357591, 157441654, 73318651, 556676242, 714117896, 787436547, 344112782, 58230671, 845667218, 189779993, 248010664, 93677875, 283457868, 531468532, 625146407, 908604275, 440072800, 65219200, 973823475, 413896268, 479115468, 452938936, 866835204, 345950665, 798889601, 665724798, 11675456, 810565057, 476289848, 487965304, 298530354, 774820202, 262785499, 561315853, 336136048, 598921547, 160237393, 496373441, 95294981, 255532374, 751905815, 847200796, 102733163, 854638978, 701839767, 804572930, 659211901, 361051661, 165624584, 824836485, 185888139, 351512723, 176349201, 362237340, 713750063, 890099264, 252336597, 966086660, 856185917, 108522507, 74609160, 930795077, 39317577, 113926737, 44721807, 84039384, 197966121, 242687928, 326727312, 524693433, 767381361, 94108666, 618802099, 386183453, 480292119, 99094211, 485277664, 965569783, 64663987, 549941651, 515511427, 580175414, 130117058, 645628485, 225803892, 355920950, 1549428, 227353320, 583274270, 584823698, 812177018, 395451281, 980274979, 792451990, 187903264, 168178236, 960630226, 148533483, 316711719, 277341938, 425875421, 742587140, 19929071, 445804492, 188391625, 208320696, 654125188, 842516813, 50837502, 704962690, 547479496, 598316998, 303279681, 850759177, 449076168, 752355849, 603115019, 52191180, 804547029, 407662041, 459853221, 264400243, 672062284, 131915498, 396315741, 68378018, 200293516, 596609257, 664987275, 865280791, 461890041, 126877309, 992158100, 454048134, 580925443, 573083536, 27131663, 608057106, 181140635, 208272298, 816329404, 997470039, 205742330, 22071727, 19541759, 225284089, 247355816, 266897575, 492181664, 739537480, 6435048, 498616712, 238154185, 244589233, 743205945, 981360130, 225949356, 969155301, 950515424, 176464773, 145620067, 96135484, 272600257, 418220324, 514355808, 786956065, 205176382, 719532190, 506488248, 711664630, 431196813, 937685061, 649349684, 80546490, 18231544, 667581228, 748127718, 766359262, 433940483, 182068194, 948427456, 382367932, 564436126, 512863575, 895231507, 459667626, 972531201, 867762701, 327430320, 299961514, 167724208, 495154528, 795116042, 962840250, 457994771, 253110806, 215951049, 673945820, 927056626, 143007668, 816953488, 744010107, 887017775, 703971256, 447981356, 334999124, 38970373, 486951729, 821950853, 860921226, 347872948, 169823794, 30745013, 378617961, 548441755, 579186768, 957804729, 506246477, 85433238, 43237960, 549484437, 634917675, 678155635, 227640065, 862557740, 540713368, 768353433, 630911166, 171624527, 939977960, 570889119, 742513646, 682491599, 253380711, 995894357, 678385949, 931766660, 927661010, 606046952, 537813605, 465474608, 71521553, 609335158, 74809759, 146331312, 755666470, 830476229, 976807541, 732474004, 562950226, 539757760, 272231757, 835181983, 374939736, 647171493, 482353469, 857293205, 504464691, 986818160, 844111358, 348576042, 335394195, 179505546, 528081588, 863475783, 42981322, 571062910, 434538686, 477520008, 48582911, 483121597, 960641605, 9224509, 492346106, 452987704, 462212213, 954558319, 407546016, 869758229, 824316541, 231862550, 101620772, 925937313, 157799856, 259420628, 185357934, 343157790, 602578418, 787936352, 131094135, 733672553, 521608898, 652703033, 386375579, 907984477, 560687503, 947063082, 855047552, 415735048, 362798123, 217845668, 633580716, 996378839, 214224500, 847805216, 844184048, 58408541, 906213757, 750397798, 808806339, 715020089, 465417880, 274224212, 989244301, 454662174, 728886386, 718130680, 172792847, 901679233, 619809906, 792602753, 694281979, 314091878, 106694624, 800976603, 115068474, 221763098, 22739694, 137808168, 359571266, 382310960, 520119128, 879690394, 262001347, 782120475, 661810862, 923812209, 705932677, 367743532, 291555734, 997488411, 365231936, 656787670, 654276074, 19508003, 676295673, 330571740, 350079743, 26375409, 356947149, 707026892, 733402301, 90349443, 797376335, 530778629, 621128072, 418504400, 949283029, 570411094, 988915494, 938198516, 508609603, 497525090, 435723599, 944333202, 441858285, 877581884, 821915079, 263773357, 141355234, 963270313, 227043663, 368398897, 331669203, 558712866, 927111763, 258780959, 817493825, 744605581, 3386533, 820880358, 565485932, 568872465, 389752816, 955238748, 524111206, 913864022, 869102763, 393213962, 307077977, 176180733, 569394695, 876472672, 52653398, 622048093, 498520758, 551174156, 173222242, 671743000, 222917149, 396139391, 67882384, 290799533, 686938924, 754821308, 45620834, 732559758, 487381059, 533001893, 265561644, 752942703, 285944589, 551506233, 304448929, 590393518, 141899744, 446348673, 36742184, 178641928, 624990601, 661732785, 840374713, 465365307, 127098085, 967472798, 432838098, 559936183, 527408974, 960247072, 520183248, 47592215, 7839280, 528022528, 575614743, 583454023, 111476544, 687091287, 270545303, 382021847, 69113127, 339658430, 721680277, 790793404, 130451827, 852132104, 642925501, 773377328, 625509425, 268434919, 41812240, 667321665, 935756584, 977568824, 644890482, 580647059, 558215876, 203106351, 783753410, 341969279, 545075630, 328829033, 670798312, 215873935, 544702968, 215501273, 431375208, 976078176, 191579442, 622954650, 599032819, 790612261, 413566904, 12599716, 803211977, 216778874, 229378590, 32590560, 249369434, 478748024, 511338584, 760708018, 239456035, 750794619, 511502630, 750958665, 501753277, 13255900, 764214565, 265967835, 279223735, 43438293, 309406128, 588629863, 632068156, 941474284, 530104140, 162172289, 103646566, 633750706, 795922995, 899569561, 533320260, 329243248, 228812802, 762133062, 91376303, 320189105, 82322160, 173698463, 493887568, 576209728, 749908191, 243795752, 820005480, 569913664, 813709416, 633714889, 203628546, 17337955, 651052844, 854681390, 872019345, 523072182, 377753565, 249772903, 772845085, 150598643, 400371546, 173216624, 323815267, 724186813, 897403437, 221218697, 945405510, 842808940, 64027630, 9433133, 852242073, 916269703, 925702836, 777944902, 694214598, 619917427, 397862322, 92076913, 711994340, 109856655, 201933568, 913927908, 23784556, 225718124, 139646025, 163430581, 389148705, 528794730, 692225311, 81374009, 610168739, 302394043, 383768052, 993936791, 296330827, 680098879, 674035663, 970366490, 650465362, 324501018, 294867501][S])

    # D = r_int()
    # C = R()
    # S = [R() for _ in range(D)]
    # # T = [r_int() for _ in range(D)]
    
    # def calc_score(D, C, S, T):
    #     sat = 0
    #     satl = [0] * D
    #     DI = [0] * 26 # daily irritation
    #     T_ = [t-1 for t in T]
    #     for i, t in enumerate(T_):
    #         for j in range(26):
    #             if j != t:
    #                 DI[j] += 1
    #                 sat -= C[j] * DI[j]
    #             else: # j == t
    #                 DI[j] = 0
    #                 sat += S[i][j]
    #         satl[i] = sat
    #     # return satl
    #     return sat
    
    # def donyoku(D, C, S):
    #     # return T
    #     DI = [0] * 26
    #     T = [0] * D
    #     for i in range(D):
    #         candidate = -1
    #         candidate_value = -INF
    #         for j in range(26):
    #             tmp_j = (DI[j] + 1) * C[j] + S[i][j] # merit
    #             if candidate_value < tmp_j:
    #                 candidate_value = tmp_j
    #                 candidate = j
    #         T[i] = candidate
    #     return [t+1 for t in T]

    # def emphasize_c(D, C, S, emp = 0.9):
    #     # return T
    #     DI = [0] * 26
    #     T = [0] * D
    #     for i in range(D):
    #         candidate = -1
    #         candidate_value = -INF
    #         for j in range(26):
    #             tmp_j = (DI[j] + 1) * C[j] + S[i][j] * emp # merit
    #             if candidate_value < tmp_j:
    #                 candidate_value = tmp_j
    #                 candidate = j
    #         T[i] = candidate
    #     return [t+1 for t in T]

    # def update_one(T, score):
    #     target_t = random.randint(0, D-1)
    #     after_abc = random.randint(1, 24)
    #     before_abc = T[target_t]
    #     T[target_t] = after_abc
    #     tmp = calc_score(D, C, S, T)
    #     if score < tmp:
    #         score = tmp
    #     else:
    #         T[target_t] = before_abc
    #     return T, score
    
    # def change_two(T, score):
    #     target_1, target_2 = random.sample(range(0, D), 2)
    #     before_1 = T[target_1]
    #     before_2 = T[target_2]
    #     T[target_1] = before_2
    #     T[target_2] = before_1
    #     tmp = calc_score(D, C, S, T)
    #     if score < tmp:
    #         score = tmp
    #     else:
    #         T[target_1] = before_1
    #         T[target_2] = before_2
    #     return T, score

    # import time
    # start = time.perf_counter()
    
    # T = [1] * D
    # score = -INF
    # Cand = [donyoku(D, C, S), emphasize_c(D, C, S), emphasize_c(D, C, S, 0.5), emphasize_c(D, C, S, 0)]
    # for c in Cand:
    #     tmp = calc_score(D, C, S, c)
    #     if tmp > score:
    #         T = c
    #         score = tmp
    
    # import random
    # while time.perf_counter() - start < 1.8:
    #     if random.random() < 0.5:
    #         T, score = update_one(T, score)
    #     else:
    #         T, score = change_two(T, score)

    # print(*T, sep='\n')


    #%%
    # end of main
    # ----------------------------------

    """memo: how to use defaultdict of list
    # initialize
    Dic = defaultdict(list)
    # append / extend
    Dic[x].append(y)
    # three methods for loop: keys(), values(), items()
    for k, v in Dic.items():
    """
    
    """memo: how to solve binary problems
    # to make binary digits text
    >>> a = 5
    >>> bin_str_a = format(a, '#06b')
    >>> print(bin_str_a)
    0b0101 # first 2 strings (='0b') indicates it is binary
    """
    
    """memo: how to solve the problem
    creating simple test/answer
    greed
    simple dp
    graph
    """

if __name__ == '__main__':
    main()