from collections import deque


puzzle_input = 59756772370948995765943195844952640015210703313486295362653878290009098923609769261473534009395188480864325959786470084762607666312503091505466258796062230652769633818282653497853018108281567627899722548602257463608530331299936274116326038606007040084159138769832784921878333830514041948066594667152593945159170816779820264758715101494739244533095696039336070510975612190417391067896410262310835830006544632083421447385542256916141256383813360662952845638955872442636455511906111157861890394133454959320174572270568292972621253460895625862616228998147301670850340831993043617316938748361984714845874270986989103792418940945322846146634931990046966552


def build_patter(position):
    pattern = []
    for p in [0, 1, 0, -1]:
        for _ in range(position + 1):
            pattern.append(p)
    return pattern


def fft(digits, phase):
    for _ in range(0, phase):
        for pos in range(0, len(digits)):
            base_pattern = deque(build_patter(pos))
            base_pattern.rotate(-1)

            res = 0
            for i in range(len(digits)):
                res += digits[i] * base_pattern[0]
                base_pattern.rotate(-1)

            digits[pos] = abs(res) % 10

    return digits


if __name__ == '__main__':
    fft8 = fft([int(i) for i in list(str(puzzle_input))], 100)[:8]
    print(''.join(map(str, fft8)))
