PalindromicBorder.py

from itertools import product
from functools import lru_cache

import time


def timeit(method):
    def timed(*args, **kw):
        ts = time.time()
        result = method(*args, **kw)
        te = time.time()

        print('%r (%r, %r) %2.2f sec' % \
              (method.__name__, args, kw, te - ts))
        return result

    return timed


# def is_palindrome(string):
#     return string == string[::-1]

def is_palindrome_border(string, sub):
    size = len(sub)
    return string[:size] == sub and string[::-1][:size] == sub


@lru_cache(maxsize=None)
def count_palindromic_borders(s):
    total = 0
    for i in range(1, len(s)):
        if s[:i] == s[-i:] and is_palindrome_border(s, s[:i]):
            total += 1
    return total


def gen_substrings(string):
    size = len(string)

    for x, y in product(range(size), range(size + 1)):
        if x != y and x < y and abs(x - y) > 1:
            yield string[x: y]


@timeit
def main():
    # string = input().strip()
    # string = 'aaaa'
    string = 'bhbebhbaabhbebhbddbhbebhbaabhbebhbgbhbebhbaabhbebhbddbhbebhbaabhbebhbhhbhbebhbaabhbebhbddbhbebhbaabhbebhbgbhbebhbaabhbebhbddbhbebhbaabhbebhbhhbhbebhbaabhbebhbddbhbebhbaabhbebhbgbhbebhbaabhbebhbddbhbebhbaabhbebhbhhbhbebhbaabhbebhbddbhbebhbaabhbebhbgbhbebhbaabhbebhbddbhbebhbaabhbebhb'
    # string = 'bhgfdbgfccfdfebccedfagbfegdfedbfchdfabcdeagbehdheheefgbbefhaaafdhaaacddgdbhhadgecdbhbcafhhfahcdhddhfgcdbdcbdfhahcbgddhadgfdgagfdbeaagdbbfcedcecefbabaaegghegfbbgfbgdeaebcbeefhbdabeabaghhdfeegcchbfdbcfddbaaabdachadhhdgcacghfagggchahcdacdbdhbfgcbgbeedehbdecccaebaddddggebfgheaacbegeaffebhgdhcehfacagbfhgdgcdgeecdadafhcfffehceecgeahbhgegahefdhadcabbcggacfcgbeffeehdcdbddgagfachadadbgdddfcebhbfdaagecbhabffbhebceedchhfebbfaccdddbhfcgfddcedggfccbecabgbcebegehbgggaedeafaddgafbbbdbcbcefdbeaafghegdhcdfdgabhgcahfcchegeahaaagghcecbhggcehddfgeedggccfhcehcefadhfgbeehgagbedhaadggfadedaefebgabdgchcbfcaggdggdbecgffdafhfcadcbgadfcfcefbdahbeagggddbdbaadbefccfgahdcdadgacaecgcbbgcehdeceahgdeeddhfghbfadfegdhhefbaeeegaffhabddedaccbhcfehdhgcddddhaafafchfddahgabacbdhfccfaeadhechehabbhgecgdagebafehdgbagfabfedeacebdehhgfchegaeeeehcfhadhbaeeeegbgbffaddcchacdeghdafcaacbagfecdfaecgegbgaahdddbdhcabcadeabbeefcebecgcdedddghhhcgbchecdacebgagafafhghdccggaffahdbbcfdfffchecfehfbhdbcgdaeegbefefhgdceaagheafaacchgdbegbachbgffeedhghhgfhcgedggffeagaghabhbhegdaccgbcfhbhffcddhaahgagfbhecgabcadehegedhdaegdafdafbadhbcdeaefceahdefhafdabbebghbdbcgadadhbhedeechbahbfcbgdfabfbfgddghebgfbdafhdeaddbafdgaagcfahddcbcgdbdeeebdhfecbfcgaahbhbghacccdfbggeccadfhbbbchdahehadahcabedebedhafbbbhacacehfehbeheeggfhdaeeeheeefffeghfadefadheddabcfbfffbbefgaddghbfebbbhbegfhbfbddcaahccdhadcdbcfhggahfbedgdfdeaggbhfdbacbefefhbefaefffbbdeghbgfhhefcfffgbcdhbedgeadcfedbbbachfbhcgbheggfabebfaacadefahgbagdheeggdafhgdehebacbaebeagehffhdagheffhfdgdgdcdedffdbghbedabahfafefccehfdddgfgcadheefdfbhfdheaacefegbedehhcefefbdbfaedcdafdffdhbadabhdggcadafababgbfbdbcaehfhgghbgabcghehceecfedefbfachaggffeeegcehedgbcbfgddchhaaeacebacgfhcbfffebacccdaahddgcdggdaceafdfefgbcdfeehggdghcbcadfgcagefgbadffbgaedeadchgbgacaagfgafeeccgcfdagcacfedagcghagcagafeacaefcchhghfahafddgcfebfddfbdcgdegabbcbaaagaaggdbefgahddcafgcdbgbbacebdebbfbhdfahcghbbdebacdddbefbhbccfedcfcfccefaegbhcchefcaggfafgchdgcgeedggadgechdebcbgebfcgfaehhhgcfcgbafbedfgdacecddgeaacfageagccdeaefffbbchecbaefdcbddeadcfdahfeegabdgceabadcbhhecbaffaahfeafbebhecdcehdfaghbfhfhafefgfedbeacabcfdfhheceeaefgddfdacaghecabccbeeghbghgadcbhahcdefdgfcfcefdgaecedcgbbebegcegbgbgefebhcddhgbhdeeggchhgadedhdegeccbhdabhdaffaabeghgfgegbabbdfhaabbhecadfabcabdeaccfagdchedcccccdebhgbddbegcfbgfebdehgggdbbfddhghagfbbbcfhecadaeedbdbhcebdbegadgabdbceehdabedbahebdgbfccaeggebefcageecdadfeggegdgbbhgdbghheebbbdbhafcdffabdhgbcecddageggddceedafcacedabebfdhgfdbagbgcaegdgchbceecgaggccahfhfcdgcbaaeafcddecfhgbbebhddbdcgcaafgchgddgafbdbdaabbcgdbbgdebbgbcehedghgehdgdebdfdfhbaacgdghfeahaaddgdbcceafbcbgfgfggfaebgegcefdeagcdafgefdfhedecacagcfhabfdfcgcceegebebhhggecdgcfhaaehafedcgbebgbhccddbccagedfgaehaagbfdehbgecefbghecbhebfaecgegffgegdhcdaahdeeeddbfeabffbbahggfdfbbaaddaecdagadcbagbbegcfgcdfhgcahcadgahaehhedbfdhgfdehbdbeaadcaceafcbedfecbhdgccehgahhdaddbgfbbccgeddhahbbgehahdafdhehhhcagachcefghaghhhafehgdcgaffeeedhfbhhabdghcgfbgfbdbabecheheaebddgfcffdadcccadafedgefcgegfbgbcbeaggfebfhehbecbbgfhccbaghfhfhbgdbfcgbddahccdedecadeceebdcaabchedegcfcffbahfedbhdfdgbahfchfdbehfaghfaedbecgbfaabfdhgdgdffbahfaeggddghghebgfggfhdagbeefbcgcbdcfbaafghdfdedadbfcegbgcfddhbfaehfghfdffgdadgbgagaeebcghfcgghhdhebgceehchhffadfhecdfececedadcdcgebaafhdehabhehgabcffechafadhdgfahgaefdaeebeaacabefhahgaegedccbcbhcfegfbcgfchhcaehhehgfdebhgdaaehdbdbgedebfdbhefgdbfbgbghaecafghahcbfhecabfbabggfaeggfegfbafgheggghefdggedhefgccggaedfcagdfecbcaabefecdagdedbgfhffdacgbabgedagdahafdcbdaehdfgaedghdafebgdfbdefddfahhbcafcdcaegdcggcdddcgbdbfaeafehfgcfdeageeehgcfbgaeagfdhceddbacggedbaeheaedhgbaebeeacaheedhfdcebghchdcdeghdeadbbhfbbfbgbefhhhdagccfgeacchfhhaabhfcbddhehedgeggcbbhhfhbahghgghhfecghffefchdggcahdhgaghaffhedgdadfhcdegaggdeefedadbbcabhfbdahhacehfhedhcbdhfadabhbcbbdageegedhghgdhchgfabegchgdgafhbaaafegbhfhgedfgcedcfhahhhcfhhfaafafbhgaefgaaehcacffcffbehgdhdehaeebdcbahaaaehcechbefgfbgdffhbehfabbccbbcbbgbecddehacecahhfgabgfbhgdbhfebgcccffgbegdaaehhbghdefeddaedfaeddggadebhcehdagccecfahbdcbafgabcdhadceebgbabbheddgaefchhdhfcagedgehaadcgecagbebfccbheaghadbacfdabcabgcacfaagecdgeefafdhfhbfbgabadbbbebdbbehfgddchaceebbdcgebhfbcgcdcegdfcddaggcfhecdgdgaccbbhcdffgabedghgbheacchgecehafbcgcbbfggdghacfhahgfhahghdadcaaechgdaebghafhccgcbfhafggebgaegaaahgdhcffcfcbhfabgfbhchfhbehfchfdhdgggdeaagbhdbbcgcbbbgacchhfgeafagegcagcghccbdehffagdabghadgfddfbhddhbggaaabdebabbgechcbafhfadcccffcgdagdaagebgfcfbeeegebfbcadedabfgfffaffhbgfgachfhdddfafhbadebebhbgecdbbehgcabbfafadcaabbbefcagbcegehhfdhdfheheeeeageahgbddddcffgdbgcgbbchaggedcadafdhdfcgafafdhaefddgefffddbgfcbfhfeccgacebahaadfdgdadbfhegfcahhheebgccagdafdbbaehdedebcbahdagcacgbabdbhgbfbcgbhffdabfccfcffaafdghdhcehbgecacehhbdacacffeccfcaabhdabahcgdfgfbgfcbfebhbgeeabgabhheabehdcdababhfdacabcbhgfhheaadhedabdedgeeggdebdgbeaddgadfedfaccdddghgedddbghdcfegghceafceahecbafegeddaggbefegcbfaahfaehfegbgabeeaahdafbccggaahfbaegaaffedhddahaahhdafechcahdafeabcachggcfbgfaggafbacgcbacbdcghchbdbabadgbbdchbcedchbeabgbfbhedhggaghabfccbebcggfafgefachfdgbhfhfggfghcacdedgcbdcgcgecbdhebadhabfggdfaeheadcdeffdhehbfcabdbfcbghhedeeheahhccdaaghefbbhbcdchfdffcbahghdggcbbfbbeafbbgbdaefabbfgdhgcfffdehefffgbgdchbdcbhabbbhhegghddeghedebaccgfeggaaahababaagggfbbbabfdfgdaacffaefaeebffcgfaedfgehgfebddeddgaagefhacaghceedahagdhebefehchcahdheagecgcbagfdheefadcbhhfgbebcdebhehehfgaffgbecfbcaddadageehgadhhagdhdchbhfcdahechaghdgghdfgdbfcbegahahahfccfbghbgfabegbhehcfeegacgacfabcddhechfaegcaedhacbfggdhabhdhhebcabhcaececefhhehbgfaeahecghbfecaedhgddaagfffebeghbgdcfaedhfadhahdhfgdggbddghfcfeedagaacdhhedgecbeaahggabcgahagdebdccdefddbgcgadcadbgcbhehadhggehcgbfdhagagagheahhbgbcffbfabdhfdbdeggdhfeffcebdebecchhaafabahgdacahadgfhddcaefefbgaafabcacdabgadghdcfbbbedbaafgcdgcagddgggghehcdgffeggfccgdcdbeghhgfcbdahchebbhhhedfcaaegdhbedhdcgafhdfhffdggcgfgbdacdfagecchbfchfhhaeggbbeadcfbeabgdggbcadccaebfdaghgebhabcdgdhhffcddegehagaehfhadgghhgaaadhecgbhaececgeceegebfefecedaeebhdfbbgabcdgfbchgggchdgehabdbfhcfchgdfhehccedeebccdcfbgfchadfhfcbeaebhaabdffhbgcdceadcffcfahefbfbbbcbcdcfahebggeacedfcbhhbgehhbaaddbfgecgdghbfdbhhfebgdbhbfgaghbbccgagagchfdeafdhcabadchfhgfffghhbfhhgfbfcfbccebeeceaedfdbcbgbafcfebdbdadabfcghgcbccgfhbhccfdcdfahgdbbeebfcddbbgcdaabacaceffhachaacbcgfdehhhaafdegdfgffaccfbdhadhcebbbffbeebeceaaafgfcghfdaacadbdhdeaabbefdahhbhhgffbdeggfgafbcaafeaffcbdfbceccebhbcdfabcgcaheahbfhgcbhfgaaddchebagefggaeaadeacffbdadcfbcfefhdbbdhfbfdbbdbehbgehahhdbeeecbbbedcacabadcbhdggeeddeccheheabfbcbefbhfchaeahhggedbhhdchhbdhcabebfbdegfdhcegbcefffffbheaahachbgagaddgbgfdceefaccghhhgdhgchabagchgfcfgacbdggahacfhceffddaddbdbdcabefhfhbaghafhccgegdcbgcebdachccahhhehaefhecggeedchfdfhagcabbcdbbdbfcbbhbfbhefehhdecbdchfcahfeaghbebdfaedbdhghgfdchefcdceebbacahdeagbacebgdhfbeaddeafadceedegddchdabddfebbdgchhgcdgadbchgfdebggabhbechadadbccaafehfhahhgecdfbbgcahhcghfgdhbfhbcdahdbgchdecafegaeghhegedbdehdfbggbbhhdgcabdffbfbheaedfheadddafcggdffheahfdececdegeabbhgbcbfcghbecgcbccahffbbhfffbfhcefdggabfhcbcadddfeccbeeabbfcheedbhcaadfhfgbfcfahbdcchgcahhcgegcffeffhcfebgbddccefegecaecagaeecbbghhfbebccdfgfaccebghbcbbabfeehfcgeahabcdehbbhddeebdgdehdffhbefecbebcfdfcdgdcbhggabeefdhdaheeeagfeahcdeegchbeghchbgdgbcbcbggfgfddfcfahbhbaafhhhgafbhhdabfghcfefabafchgbagbgfafdbdeacaadfhchehfeafbcehdefecdfaggddgfdgaafchbbefcbgeffacdeegbeehhhfeceecbhcdagacahhfehhhdeffaceabceegbghaacahddhccegbegeadbafgahafdggbfgcagbdbafdedeabbafcbcabbagegegecaebbhcbegfhcgbdggghagbchhgfeebgefhfecgaaeaccbgaheahcbbbaaheeadbgcgcefdebdhdefddbdcdeeffeebaeebchafdfaagdhbheecfaeaeafbebdfghgaggfcdfcbabchfhbchgcdgafdbaahhgagffaadccddedadecccegbedegdefccfahdaagccbfgefcbhedeceafagaeedhbdgeegcgaeehabbbbfffabffceggabfbeegacahdedcfedgfadcafagheefefdfbhdcbebeaegfabegchaceaadeebabegddbfefgbgchdcbhadhbfdbghgcageeehhgeddcebeefgfehadafhbdghgggcccbbafeehbfdfcbchaccahbcdhbbfhdhceacbfgageddgefffhafgbhbbbcgafgcbgfcddcbhfegcbdhadehfeagfdefacacbfeeahgaecggebfefcdcgeadheahhabafgegfcgbfeabfffchbeffeaebbdabfahdefahdbehbfehchgddeaaeebfabhfbgafdaegbafdfbcaaadeeeebafgagffhdfegfbehbbchdehdechbgdchaahggffbccaadehegbdbfcebfecdhecafcgdheebgebbbafhbbagdeaaaceahgaeaghhcdbaacbbdhaeaaddedeffafegfahdhggdhgdcaefhebheecahgffgcbfhcedbcbechhehdbghcfdhaeggbdfefcdhggaahfcheggahfhccdbchhbadgeaaahgghggebfbhdbhaabddcfcbgdeeheehdcgdbehcbabebafcbafdfafedbacgfcbhaeaeecfeebgegaggfbefgaaaadgffhffefbaageehcagcgeaaafgaggbbeggeddabeabcefbhfhbeebeehcffbggfeebahbbdbcfghgfeggacaeghhdeabcfgghgfahacbfaadfebdfddbccafgahagfgfddfcdhdahdeehfaebdgdggaehhffedchhhbchedghhdheddfgbaeabbhagefbgeafgdecgdcfgbbbehhghegaffbdbgehcfeaabdgefdcgedcdcadggdddegecddfaafabagffbhdfcgbegedfhgaeffgaadaababbgghhfcehafehbhebfefcbdcchccacebacahadehdbdcdcgeadbceefgdhbdcffchfchaghehcgcffgfahheeedheedgbaaafcagahcabacgfbdfadcehfedbhbchcceeccfbefdfhbcafabacfhhbdaaechgeedhgaadfdaefcfccgcedbdfedfbffhcbcbhcbchfcecfbehhgechhhedffacecdhdcbffbchfeegaefgahfhhbcegdgdfbcbddgaeaabeeheaecaehadbchhffcdgeebacceccgggfchcehgdhbecaehfgcddgedaghcafahdcgfgfdcfeghecgbbbeehahahgchedghfeeechghdeghheaafeefedfdbhdfcbeagaeahchcgfbfbbfhfbecebfgaaddcadaahaabhcheefffcedeafabcgcdcffcafchfcaefhabefghcbdcgdebcgeedbgdgacddchabhbgehfgbabhdfafdebgfhbdadgdffdgeeebdbhebaeffecabeggdhcdcaghgbgcfcdbedffdbcbgfbhbafehhacagbgahafcegghedcfgdddfcefaaehaghhafhhgebcdhbhddebhaeecabcafcbebaehhdfdfhgeafhdcaccegeehhffbgbcgfbfagaffhcfebbgcdagcfdbeagfghheebbfhbcfaecfgddahegbbbcfbbchabdfceccgehgbbdhfhhedffehhbaadabedghaabgeaefbaeghdccbhgahhahcaagegfeggcdggaagfgfabhbafbhechgchfggccebehhdahbfghfhghheahacghffeddggahchhfhgheegcdebdabcbeaabfeebccbcfabcahbeehghehcebeffefgcbcdefegceheeggbcfhcbhegabdffbdhcfcgcgeeddbhchaeeagghdehehebahbdedbhcgdfbeeddfaafggebcdfbhhcgafcdgbfefcgbhbfebfbadfbfahghgafgfhbebhagbghaaeebbfbecdbccabaagggghchgcfabeabbfcccehfhahbabbbhhhfgbefdbfegffhcabfeacdbbebcfccebhccehgfecdcaceaebeedhffdhhabbedbgffgdccggegabgeccbgbgdefceheacfghcedehbcdhdefhhhafahaeecadgafdgffdaccbefahcfhbehgeggadaaghaecgbabbcdcgbcgdhfedechdahgahehhacfbchcececdgagffcacehfegdffheeagcbabeedahhhhfefafheeebdhgagcfgbhabaegdefcdeaabafaebefeddfcgcahbaabegebdheahebhbcddgbhceeecgebhfcabafceeheddfcfhfagghadeefcahcfbchbhbfdabgehabggbeeaeheafhbebgfdfgdheghffdefeddfhagehceebfacefgbebaahafedccafffefdafgfbhcccghaadbadaabfedheaebecffhdcacecedcedffdbgecdafcefgfbacghfaaafceaebdcggdecfhccbghaeaaghaehaeecaehbhbageeabeddfbcffcgebgabgefaechgbaghecafgdaeecbcfhggfghdcfeghdeaecaafagddghhbbbgahegfebhbfgabcaffafcadfdcfddgebgefebbgbcdhcebdbgdhaecghedchbhahdgeehcfcfeecghdedcfhfdgbgbbhabgdhchhefbcbfehfheacbhhefacgbbgdhbccbbggcahaehfedfgeefabfcahdgccaeebgdhadgaaffeaccegheaegadbgfegcahadgahfbhcgddbfhheehacheegbaedaedecedhfccdffeceegadgddchbehfhhbddehgdeafhfcehhafhdecggbhcafcagfdcecgacdhagdhfdfehbhfhafcbcebabedfgbfbeebcaahdfecgdagdfaehefhfcccadhbadccddchagbhbbfegfbfbgfgahabdhcdcffgahfafghgaedgbeeccbadaaedhggcdeaddfebddhdaccbggebheehfadegbgcfgfbdbchfbcfeegcccdbhhbeheagfhadffebhgaehcbdhhgbcbdbbefaafgfegaceeddcdhcfafehdgbfbcgfhgfffcbdddhhgccbbehbbdbfbcccfahegebdhdhcggbfbdgchfebbfgchafeaebgbccafbcehdbahhdgfhhgefadffafcbeddgdbhffgaghhfcgcbfafdbaagagabcdfagghddfebedggbbhhbeccfcbfabhcfecdcbhfhdgdgecafbhhgbbddcaeehgbdbefcdcbgafffhfcaebgfdbafcebbdcfehcgcfabffgcedfehgdebeehgbaaedfachgeegfcddehgbefahbbdgachbcdehdggbcdaafddbdcdhhdgbebhfdggfbceeadfcgfcdbgeeahdhcbahchegfcdgeacedagbfbeghachafgcghbbgfhehccdcfhffggchcbgddfdbdfhchabehfechheehcbfaeedfcgahbbcgbffbgcbdgdcfhhebabceffbhdcgedbcegagechhacbfbacdbdffbchafbhbeadbgdhcfgbfacdbdfeeabbbdacabbbgbfhhagbgecdeegfhdcdedffhfhhhabfbgeagcbegdacaghhcbdgfadefddedebfcffbhhffcfhcehcgafeffhbccfhgbadegaffhcdcaceebgccdghafbdagcghcbdabagbdbdddhhfgbhbhgcehfefhcfbdacfbagebbheagbghaaghccghhegbbhfbbccbagcbfhbdaacbaaacdgbcchddgafachbcgedddfhdfbefcehfdahfhcbfdgfffhadddhgagbfhgcbcbgfbfdaaegdcdahcadfecdeafchdebfghdhfgafcgaebadebgbfafbacdafabcgafffdfcfdcbfdfbedcbehcebgeggfbeggbdchghcabhdgahbdafcdcebgcheddccefedddgeefhcghebhbdcdhdcccgffahcfdfbhdfdbeghdcadddfhdbbfdhcbhcdefafeecafhgecaefdhdccedhhccabedgbedgaggffebheffheachefgdaaebehhgddedbcaggbfcgcbdcdcgbacbbgcffcdbfhegbfehgbbfedaggcfhchadfdbcfedceaaffefdfgabbaaacfhfeaabdbdaghcchchegehddafeafedceageahhcchabbcadbebgeebebfegchaghgcafbcaacbbecefgfdcbegdcdbeccccaecgfegfghgcbchahdcahbdbeffghhahdcfagdfeddgefgeebhfaaacefhcehdecfbdefaaaehebfbggadgadaebagfhbbbhdedafdabcechfaffdefhebaeafdbhfacbdcghchbgcbecgbgchfhafdachcbecdfgfefhdggfhcagdgacdhdaddccfegahdgfhdedbcabeahaghcbhfbcbeegacghfeefhbabdacabbahacbhacbbgfhghggfccccdcdhcfhdghdgbegbghcffcdeabbcedehfhgaefdcegbgchhbgcgdebaedbghfdgccfchcgbhecfhbeaaggdchdgcffbcaaecfhbhfdgbfdahaahggcbgghadecfecbhhaagfdfhbahaaahhgbaehhfcehhabbhabaghddgeefeefddefdaedfhheghfhhfbheachghdddabhdfehfacdhbhgaffhcggggbgeabadbbcfggedhggghgehdchfafehgcdgddcfeeccdggceeadcfcfhbdhhhgfbceefgbccdefbchfhaabfdheecddbcbcefgbdadfdadfcccbcddhgcdcehgfbhhfefghfcebchgecagedbebdhehgcehbdefadegfahhafdcfbgbcccfcgeaaaabdegehccedbddghfdadedghaaffagfahbfgfeahbdaeggddbehghffhfcefacgaddgahghachfafaegededabdfehcebaeedcedbdddcadhbhgfccbceehadcefcbbgdgbebehefddgcbdfeehaahaebebdfcbbacfchfgeabccdfhhchhcghghdhcbceccghefecbeedhhbggdfffdeechdfafbcahcefghgddcccdaaggfdbbheadbbacdabffgeefhhhbbcbbahgdbhdfhggagaehbbeafafehefaghbgghbhgeefccgbccaedeebebfdfdddcebadcabhegbhecbgcfcgbdccafhdacfedghggafchgbdbdcdaeccheehcedcgahcggaehfhgdabeddaehcgggcgagbdfbchaahehedfhehehcedcgbaeegfchahbcgbcffcbbhbfgfebbadhbddfcaabahccgdfdbhfcgghfddgedbdfegcghcahcccaghdhgabegabbdhfhaaefhgdgbdfdghdeggdehebfechhcegcfchebdccghfehaafgdcfhdddfcdhgbcdebhfebhdbehaeafcdhadcdgafbhddbhhdgehadcbhcbdcgffgfaaahafaabdbaceggegbghaaadchbafgafhhgeagfdhfgeeeacggcghccbbdbgbceabcfbacfhaddehdgfcaebdgcebedcghdhbabbcgacbegahfgbfccaaffbbadhhggaghbbfbdgfchfhfgehbfhgcahcdgbcebaecbbdfabhhggeecdfhcdbccdfaehffabhbcdgcefbcdfggaefchhecccchbhebaeddhbfdhhfcedafhghhfebhgdghddbdheggfebedghhbhebfeacabcgeafhdgdccbaafbeahdabdecaacdadfghfehbccdfdefbfbbffbgagaagcdhfafegbdhefcbbggcehdbefhedhfbbaagbgchhggddaeehcgdcceghddccaddaebbcdabbgffhbbgeabgcfebahdchgfacgbebcgdadahebfabggdddedchfcgccaadfcfdfggffcgddabbdfeaahhgbfadgbgddegacefhgdcbdedhbhhbgghheaccbbfefdehhbgfebhafchgbghaehhahccadheacahbbfhfggfdaebbcbbhabhhdchgbdgedffecebbchecdgeghffhgegbgfhaafedcbhfgagahcddahbheggdceebbebbbfeegdbeehfdbagchhbdfagaedbghchaheefhfcdehhghfagfbbcbacgddecfdcehhcheecbdbhchhaeabgcbbaeeegchbghaageeafhcebbdbfeddgeegbbchdbabaacgfghcgbhhccbhgeceahcbaebdgbegcgfhfebdfachddgbhagahabhfccdehbgfgfccgfhhagcdeddfbdeceehhgcdfdbdcgfeededdcfghbbeceaebedadfdabeddcbhgedchghffahbddbhegdebahbbdfefgeechgbffgcgfdbbfafddceebfffcccaggcfeddccfahbbagbgbfafbbcggfabfghaeedhgfegffhfdadefdbgfefdbfegeegaachghdeebdcedfbbbchggebhcgggcegcgfagaecbhegcchddbdbahchbafhccfeacegdabehfcchbfcdaddagcbgabbcgfcbcbeccachdehebbhcfccdfdbfechdabeccaeeagedcdaeehgbcaehdgeaaddaehchhhdhfhdacdehccaecfdfdhfdcaehhgggfbgdbbddehcgbdddagadgggagchgbfeghcbadedhdggebbhbhaefgcgeffcgdhecbgcfcfegdccedcfdcbaaegebehhhgdbhbdeeabcedeahggcahcadbfefedechfbaageahgecdfbbddccgcghhcedgafffhfffcfeacgdhafcdhebbcabfeedecabbfgghecagadfaahehdfbggcdcgghagabdhhddbdbcggchfggaehgcbbeahdafecbdbegdhhfffhecgdcccbeecaeceehagadaebddaabfhfhfabhdcdhfedhahgaghdgdebhebabafaggbfbebabfdafcgfafagbehaaaabbfbhdceegfehchhhcgecdebeaaeabebcccbfffcddgdfgcfaabcegdagefhfbahddabafddabgghbdhbecfcfgbbdageafadfbddehdffbfgeeabgfdedefgeedfbdaheecadffahchdhhefeabaehgbdbgeegdacfafdggcaffhecfacgagfhhaafffeafgggebecdehaedcbdehedfdcfdacaedgcbegcaafehfacabgebchgfcdacgbgbhacdhedhbhhgabgbhdcbcageehgcaedhffcebfdcecaeehgdcafebdbfchhcecbbhdfaaacfdcbhbhcdahabdbgfafaehbfgfcgfdacgcefedhhdhhecachbhhfgbdegfcdacggfcdbfdabcafeaadbhdhgeccchffahdgefcfdfgehgbdgbgabbhhfbbhagfagahcgbabggffegacagcbabafcbfdacdgccaadabbgggcfgfffhgfbgcdhhghbcfeegeaggbfeahbgegdeeafcdacchbebhaffefdchahhaafehbadbfgegahfbdgaddfhbbcabbhbbegafgehecdccchdffeaababccbedafefdfccbbgdfafhhafeefegfgahhecachffehhfbfagfffefcacafafdafcfhchghechehabhgheddcgeegbedeeagbabagafbhbahcafbebfghbcfcgagdbeebffhgcafdbffbchfdeecfghhfafabbechbbfdccgdheecdbfhfaeehdbhababfcahefcgabbhffbaghhehdaggbggcghhbagffbdfcefhbghhfgdebddhebfghegaeefcfahheegfdffadafeeadabahaffbbbgdhhdgdhfbccgdggaccagdbgcbdhcfabahadgdddeffcadbagdaegbcadghfdagdhghfccaghgbabcahfbdecgefeedhebcdabbcdbadhbdbddabeefhcbegfhfbbhfbbgdehdhhfcaagabcegbgageffbhgbehcccgbggadaadgbfbfdcedaabgcaedeefggdhebahcadababhdedhedacfahaedfcbbbgcbfecafdagcecfdhbdbgdahhdebffcdaeaegbbbbaefcbabcddbgdafhegecbhcfhgdaaecaahccaeedhfccfhbcgfehegeeeheedgeeghggdcbcadefdghbddaabeegdacghhcfgadbdeddahadfaebdebfafddffbeeebceedhbgcbgdeddaegefdecghaeaeaegdbcgadfdedgagbadheadadbhdfahgefbfahgdebahhagabbhfbcgeefhbfhhceaheafaegaefacfbdfhehfbdcafahecefbafhabfafdbhaccfbhfgaabafbacdeheeedffbfdegcebfccehbehcefdehgagcfcgchhhcdgfhhcbbgaccaegfhdefdcaaegcdfcgaadhhfbadbdfbhdghgceceecacfehhchhfhgcagfbbcdbfbaeeegababdffdehcdebbgbaddbfgcchcgdheeaffdccghbbcfcedeeghfdfafeceabaebfbfaddheebbhfedbcchfhhcdbgddhheeabedfdhbfaacedegfddecgadedgdddadeehbagdfhdhdhdcegfbadbeaecdhfddcacdaagfhcedbaffgcghghdgefbddfgffaafbhcabgdcgahfdgebfhhbeafhfdecefhfebffabhgbgdeehfcgeddfaccehfaeefagcfgdeefcabhhhbgdebafddbcabgeggcadaehfbcfcbebccfgdfdhaebafafdghecaabfbdcdegfgbcfehadaffacffgdfcffchcdceghcdfdfcafddfaafcfdabacgfefhhadghfbebhhbecebcfgecbfdbhcgehfdhabggddhccageehgbfcehhhahbhdbegafahddccfecdagcgahaegadhhfgcgcaghafcdheadgddffbffcbdcecbbadhddgcedfhdbagadcfbdcgfdbhheabedahhgcdchcfacdagffhbhfgcggccgdhcdgbcaeehgbabeahcggdfdbabhcegfdaabbccfgbdhbeecdgabbfecfgchcaefafgbhaggcbfdgbfbhfdadhdaffahfeefbdgbdehffebdggffeaghhbhfghedebafegghcffhcgdaeafaadhhehecgbfccfagdgffecfgaagfadfahfhdeegcfdfhbffedcchfhffhdchhahgfgbbchdhdagefdabgcadbgaabdhadggafabhhehcffgcbhdhbecdccddfdeabcagcbgcgfedcdfdcbcdfeghhccefgfgbffdhdffacacffghgacdfbcedfaadfgeddacgfhghhbeehddhggehbacgbcbgagbegdcdcbdbchgbdbabhfaafcggeafeggaecdheecggcehffhgeegfcadaedfabebfgefcahagbefgbeegbcddcgdgcbhdfabdegfefgchchfedcceefhhddffeebbeceaabefhgecfcgbeafaffhaafgebhfgbbgbcdgcbdehfcabcfbhcbhcgfghedffeeghhfbaafhfhhgbfhahahcgfagbedhahfhgcahcfghegffdffcffeecfcdbfcbfabdcbcfhbedhcbchgeedbafgcbhadafdbagdddcehfdbgfafbfacfgaahhacafgbfeeahgegehaceahgfaadgbdfadhaafcfbggafchbchdghdefdfabgdgggfhgdbdehbfeeefgdbecebhhghaecgcadbggccdcdagheefhfcbbdbabaafdghdbbcadedfhdehhaegfghgbagcbgheehhfabfdfabfdfecfaachaaaagdbecfabffbgdfedgbhdfbafcceccfcaaeecbeegbffecbaachdhadecfbehghhgddaehedbcafebffdeacfeghbhebfdadgeecdafecfchghebeedbacacbedhhdcfhgadhfhbdbabbedfbggbagdcdgbccdabcaebfecafdcghfdadbceafgdehfgcfhefefdaadfdfecchdgbfcbcaeghbebhegeadhaddfgabbdbebcbddddhccagdhcbecfdcagahhbaccedefghabgcdhbggdacgfgafeaedcefeaabfgaghhacgbbefbhdgfddbeafgeccfddcbeabdbdbcefhfecdbghdchaadccafgdhcdafedghadgfabbbhaebhebchddebgddbdaghgfhcdecefddfaeeefhdbcacadgbhghgfefhabbeheaeeebbcaedcefcaddhcdfhhcghdhecdehaaabcaffccdecghbacghcafbdefgabfacfbefgchafdcdcdefbdhbbaffgdfhafbfggcfabffeaagdedfacgbddgbgeagbcdaaffagcfccfbgcedchbdcfbddfdchffhfdefbgcebafhcbceadhcaafegbgfgdeegabageehebggcacdebfebdahegeccagaaaaheegaffgafadbbagcdgchfgchhahhaageefecccchcfbdfhgbfaacgcbfdbfdbdafaehchbcbgdfecdfhdfcbadhdeegfhgdadccceedchagbddbgbdabgheddcacbdcegfgcbbebcdcfgdehgeafdeaghaaaedecacebdacfdfdcahbhdceggeefeefahbchdgbhhdecahebggabaehgadeeabfhdhhggaffdchebefacfbcbbabeefegcebcdhadffghecaahacecefdfghbeehgaaadaagffeechecgffdhbacghbadfhbfacaacgfadbccfeacbdbdedbdfbgcbhabbabehgechgeeceheaaheeahbcfddedegefcddgfcebggffcfgbbccadefghccdagacbdagfehdcebfchgdbaeeebcddegdcgfdbfbgbacefdbhchcdagheabadgghafeegcffdghhdcaceaehadgedhegfdfgaccgehdhfchaehcahhhhcfeffadcdbaddcchcfghafaefcfebeedcaahaebefchaebhghfghdgdaaaecfafhaggbchfhbehgggefdcegahgbaddfdaeegcfabchdggbeefbaafgaffbfaecdfghdaeebgdefcfbgddgdafdfcfccbefgcfccbgeabafdggcbbaecfhhhecbgghebegdfehfgacbgbdhcedebcebhgcfebbffabdeaacadegehfgdadfdhgcfahbcahhaacfadhbgdhcdfagfddacbchcbbecadcaghabhbhcbbfgbedfhehbghdaahcaceaaeabdcafdbdbdheagahhhgchgbbgefgebhgebgceaffdebdccccbbeahgbgcgegadeeedgaddfghhbcbdeceacegdcabghbcdgggehbaehhdabeefgagaeedgfffeghhefgbehbbhaehcbdhhefaacdhhaedhdcdaaefafghgcgadchdgfdghgfghbbgedbfegcedadbcbbgdbbbgeafcfdbhehdhbadhchcccefefdhgebeabbcgeefadbaebddedggfcdbhgbgccccdefbabhbeabbbeefhcefehgeghcabedeaagbbfcffdgghdehfaechcgfcagdebafbggcdahadggcbcbgcfacaghcgffdgfahdgbggbgbhfdahfgcchecfdeebchhhhhdfabdbaeafhaeehghgcbdgghhagghffccgefhebabbaffheefggbeeadehcdehghfcefggfhhfeefabchhdddehhdbchaaggcddabahafeeceffdeahhegghhbhhbffeaaebaebgagaedfaaghhcfgcehbdagbehbbacfcafaabdgbdeadgfbababfaagfhhghbdbbabcbfadaeddcbedceehfefcdfadgdeadgcedchdgdhaeddgaagfedhaahdhchhffbbadbebedbagfggfedbacbabehdegabhcccdgdhbfhhcfghcbaceccfgcbcabeadgcgegffdeefcceeeegagaffcghdadddbfcfdhcgehdgbhcfeafcadhdbhgbcbfeghbcgeacdeaedcchchcdcbgeaefdfchdbafaegchcdeffgfafhdaabebfbecedffddfabahdddaabfahedhfedgbecdafbgaedafdaagdahfghecddhhgfbchedefbfbefgafggbhfgffchafhhdeafefaacbfegdcgabebachfhbehgdgbahheehegbcchffffgbhgdgdcahbgdaadhhhdgdbhfegcbdahfhfafadfheeceefddegbaabfehafdaeahbaebdcaagdecaaffggfghcchchccdcbecgfgagggbcabcfgbddhdgccabedfgebachgcfeaghahbfgcbbcehegafcdcaheacdheadfgcffeddgefaaeegecaheahaabdhfddcbfahbdcahhaheffahfadfhefahffdaaefadhdghcfhbbegcddchabdfbccgfcgcagfhbdgdbfeccceffgefhhdacfhhafbaehhfcfbdcfgeaccfbgdaggbadahdfbdbachchagcfegfgadhhgafebfhbedgfgafbhaahgcecbcabfaadafhbcgchbaeaacbhcbgaedcffcgcchfceedhcfgegcegefgggegchahedggffdabhdacbgghbcffhdefacahdhegfcdcgdefhehadfhehebgafeaaehdddbbgedeahbhebhhggdgceeccaccecfafgbdcehcebbacahagcgbgddadgcaahaffbbafacbbebdeaedccebfhbbfebfdbdbcebhedbghcbedfhfadgfcagaehfhaaacebcbfdhefaaaghggcedfecfabcacdaehcgahbhdhaehgdfegchdgbahdchffhbfbafabfeafaaddfhbhgegaefdheaedbbfbhfdebdbbdefbdgabdgbhdegheddgeahdfchhgaabefchedbhbcgfhfedahbehbafdhebaedecfegaffchdhgadcaddfcefhaedbeaebccfaccfebadabhcbcfgecdecahdehafbccbeegbghegadabffachdgbdffafffghaadegecfbafeahcghefcchghegebddadddabachbdefddhbcdhffgdfcbbdeedahgabgcahfefbaeccabhfhccbdeeaahaagabecbeafbbffdaffhdecfgfbcfccfcafdeaeaabbbhhehebghgafegggdaabcagffgbfgdhhcgebcfhcdahhgfgbggcahbgehhbgcafegbfbhfdcfccdhaefghgfaebhddfgddcceaddfggcaafhabfgadeahfacafaeadgfdbaahgchghggadfbgbbfgbahhadhdbegcfgbdaachgaacfbagcgfegedghccahacehdhhdbhbchdhaegccdgahbggeagdbahadghgaghcfdbfhhabcgbbahheafhbfgbaeagehggebacahcbcacdabdebadcgbdggefcddbhebbeadfcehgeabbcbeehgageedghghgcaagbdddhcbeccfeebbdhbbdfececbcecccdgfgfhabccgggahchaddfafbcgehagbdehccgcdaechdcgfbhaeeabgdaccaadefcghbacbeeahgheagfecfgaagccgdgcaaahbabdfgdeecbeagbddhdefggdbegbfgaghbbehfaehbaahbddaghfefbfchghfgfeahahebddcedcfgfgfedbbehddfcbeafehgddhhgbdcdaaagfechgggbcdedheaddghgfgehbgcbhdaehcdfabhcfdfehgacehacfebgddhcghggbcdcdceafcfeafgeeggbdhhgdgabgghhadbefgedabhaggeceddhccffbfhheggebaahgfcggbgfhchefddafbfggefcdeheehdcefadhgagahcgcggahdgfaeadahhegdgdaggheggefacagaafegdecdhccggabedccbbghhdfaffggfecdhggcfaedhefdahgbaebahgafdgdacfdbdbdachdbeaeehcfahgageadhgghbddcgegggfchbcefcgdcfbcegchfagfbbaeaecgdhacbdggffbhcdbgbdggdedffdbfadedcefdhecebdddgechhagdebabfbhfedaghfchbedchhggdafdadgefgfchehdhhbhedgghbahagfegchggfcddafceefedgdhcbfbcgadefhdagbgdebgegaacfefdhefachdahgeffhfdbdgfeebcebebgbeffcghbbhahefedcheffbbbcdfehgcachgefffgfgfbdbegabdfcfgfadbabdaecgaaeggbeechfgfghbdcgchgfaghdhdffdfbbecfaeffdcdcdhebbdagdgfgfaedebeffhdfdadgcgbgffhgbhfegcdddhghadegchdfhgecffacchbdhgafadadchccchaegebgcfahcacfhdagbadbdeffdhafgabfecdhadgcdahcdabeaegeadbdcbabcbggebfeeeghegbagceghcchfedafdbhfhgbadfehddebeehhaggdafaeaacebbbahcadhecchgeecdddbbgcggghhadacebbgbefghhffdbahedafbcehbdgbghdcafabbfhaefgagghdbhaccebdhaefhahhfhageahbffbddagehhgbdhedhbagbafghgeegdfdaggdgfhfefhhfdceeddfdadcgageddhebghhdhfheegbhbgeebbhbfbafaeadeefceefdbehfcbfdhbhacgbhabeagfdcbaeffbagfaehbbdaccaebbebdabbfedhfhecafaffeegfhghcgedhaecafdgbgfgfbafgbcdfhbdghcafgdfghhhedfgbcehdfecghfdghgegbfehabgaafedccfeheheabchhffgecefhaehbchchefbgcffgfbhgdgfbedfgacfagecbeeaabcgehecefbdbaaceehcebhehdgahcbhedgaccchhecaeccagbcccbhcefceaddegbebdgadccdgeggdhafcbeegcgcccfgahcbcabfddbbahadgaaacfeahdcbfhhfgbhbbageehgegghfghfaecadfceccdhaegbghacdhahgggdffafccgfhacbcfbdcheagecbedacbgfgefegacdhcfbfdcafbefabhbfccheaecebgcbagbddcageadfeaffahccbbgbfbghhaaagbdcddahdefhecfebhhcbfeggcfgcggbhbddedchhhgecdaddhgefccdeabgghhfacaegddfccbefcaabgegahcehdcfdccdedacgdaafbfddfdfdaddhfhgbbdedfhaahcgdchaeedhbheehahgfgeghhcdecdfbfdeacfegadhhadgacefaaeahgdeagbcdegdhdhfedfddacddgadhedgdgcdedfaaedhhdedgbhbcbefheagbefechhhdfhdbccafgedadeceahdfhcgdhcggbfbgeehggaefehfhehdeggbfahbhbhgdehbaebgcbchfceegdhcbfehgdaffhdaddbdhcbbdebagfeebdgcbcbhgbedaadddegchadceedcchgddefehhdfahabhdechdegdabheebgdhbgdhccgfhgfhhecehchdacdbbafcgbbahehchfhgdegdbahacgddahebhcdfdefcaeehbegfaeabehbhffcfeggdabadfggfccfegdbhhbadaccfhecddagdbghgefdhhadgdefcffgfhacgfebaehdfgcdchgbhhefcacffhdchdefaahaegebegehgdafcfcefebddefcacaachbhffacdfbbabgcgageeahaeecegcfbbgahdabgfcafdghchggdgfdcbghaaebccbbfbcdhedehcebbcheaeacggbggfhahabebdaahdfhfbagdaddedfcbhahehaehbabfabeegdbheacedfagddhcdggdgccaddfdfbhdfbdbbffedfcgabaehghgbbgefdhcehfbaacbghfbfhhfahbhfafgcdchgcbdbgebhhcfghgdgfbgecfbddafgcefefafdegcdahchfffcgdgbbaeeabccfhhchefedahdhbdfhahfeggfgcbgddaadhcceaghagchhfeggeeccchafagadgbggdbcdhbdfddfbhdhdhbfcafhadhdcacaedchcddaggfhfagbahgchebhhadbbfbfadecghcffhedadeaccccgdbgdehebbbbegedfgadgegghcgceaeddfbgcaddbefgcbbahbdffbdfdbhhbdceaddceggfcddfeefdfabdbeaeghdhcgecbhfffddhggecdbfabgdcddgbccaeaehbdehahcafaehdgeehdhcgdahfchccebehfdaefabfeabcefcheefheefhehbaafhfahbfhcdeceggbagfedfbacaebbebhdghdhfcbagdefbffhccdhddbdhcedddgbdbaaebaceehgbffdhadcdefchbfcfeeafeabgaecedafagahgdbcagehacbfgffdcffafbcbedgfbgehcgbcegbeacbgagbcdgcahebehhbagfaadbcahdehfgffehhafbafgcbfbcghhghdhbdhehgcfehcdhcaacfgegegacfaafdhgggdfffdbefedheebccgagebabbageafcgahdfcebhafgfbahdghccacdbdcfdhhbhhfebbfbcchhdhghffbhgddhgffbeedddahfbegdhfccfabcgccegfdecaggfbbabafcedgdbaggbhahccdahgebhchedaeeachfffagfgeggffahaahheaghaccaghbagggdgeafbhdgedffdeehfcgfebfcagdgebbdfbagadefgccbggadahaeaggaebgbcheaaegbhdgffagdgghgfhcffafccddechedddecgchdcfgadfgbfagcaeechhhcgdfbgbdedchfhgfdddeadcddghgghfafafhhgcdbfdgebdhegdfbgaeehccghceahdhffcgcfehghgdfcagaadehfhgfbcfbfegcgffebecbcfgeffefabffadcbfhccdbecgbghfaaaghedebbecgbcbedgdgahhebfghedhfdfeababcedaffbbahfghefdfcbehfdeabaacabeeeebbfdceaadeggbaafhfadfbdgddhhhedbfaeheeahaggbggggdgbaafgdagdacgbhhfhdbhdbfbcdhabcgdcgabcahfabdbacghghgbadcchbcadbdfhdgbefgegcgheegcefdeafhhgbabcdhchfdddchbefaachdgegceebecdeefhdhgadbdfbfbgfbaeegadbfhcbbfffdeacdbfeecfbdehfedbdeeebdgcfehchddbgehdabacfebcbedeaaabdgdaccdbggdecchcdaeaefcfcgbcgbebahcccfeadhefbeheeefabhgdfhgdbcfbbhddehdhgaehedeahbabageggcbhegagfdbbdfabfebbafbhgbagafeghgfeefccadddaeffaggadhabbahbfehfcebgbdabgefhaceaadbdcbedbdehhdebhfaaaacgehfebcfbfgehhadadhhdddecaedaffhbeegfgdgdbcdacgaffaaadfdebgegddahagegbcccefcgdcdacebgbecccgbfcbechaaacccgheecghdbdeheabhchahbbddadeafgcdgghaegdfcheghffbffaggdcggggdeagcgfddegaggfefcchhhhggdaebgdfcddfcbaffgfdechcfbbebachdcdfagcdcfaegabdgggdbgfghgcagfhchdhabbddgdhfdaabhheafbgehafgfeafhhfbaaegdedgeehddedafbefcbdhgdefcbgcbdaehecdachdgcddehagbdfhgceaddcfgdbfheahghcecfhgeaefdbecdbchefecafhhbhghhadbfdhbddhgedaaedhaadcaabhcbfbaffbcaadddcbhgchcfgdfbffcheeabfagcbacbdfeghdebdggbbddhafgebgfggdbhddagbeeahabchheachhcefgfdddbgeabaahbeebeecgdbcedbdffbdcegggecgfcheddaehfggahaeccahhbccfaadeccbfbgaegfeddcedcafeafebhghagceaegffegccdgggacbcchhdededbddhgahcgfacdcegaceaegchfbcbegefcaeaaecgbcaeeecehgedehcbaecfdhcfhhfhdhfecfagbcdaahefggghdbegagdhfagahdebaeabgdchcgebecahdefdcacaaaaadfbdbbfaehhhfdabfabbegeghhghhhhdebgfcdfhceghhgbfgcgcacahbhhbggechchcgfbabhabfbgddefdgfdaecbcafeahecfbdgccgdhhbccfhfeeaebcfddcadbefhfafhcddbcedeccbggcchehdhbdcchhbehgdbbgcddfhfhbdgdffheahfdbhcbbgahccbaeedceabfdhaafhefgbbabdbccbbedceahacdadaedaeahbfgcggdchfeahaebeeaegdfbdbedfedgcbbahecgcggbgccdgdhegegcfcfdhabbbcbahegbcfcbheeghdcgaaafdfacgcdheeadageddgeddabcddadeabhgbbededaaddbcaefgaababedfehbfaadbbhffcffgagaacfhcgachegebffgffbggaddcababhabcgaeebhdffagcfehdffbfbfabgacfbehheedfdgdagbcegbhdgabhfbbdbdbchabeeebhdehbgbfecehbfaacbbgdfhfehhaedcdggdaeefahcaahaabcchfhgcdgbecfgfdeadbfbbedbeccedegdbfbdbhffbcdhfhhbaeccafdehfbcbhfcfhgggddafghcfgdgdfadcdabbbecabffaddhgghdegfcebahgadbddceegheaecahfhfegaaefcbgcafcdgggacchbhhfbheghbcfbdchfdfadcchaafbdaaehhcagggfabdbefabagbdaecbeachacehbghheffegagcfgefefafbdggdafdcbcdhbceghafhghefdbbbcgcfeaaegdghfbhgededdbdcbhhebafdhaadaaagdggaafgeachdecffcebdfhgehghhghgbgebgbhcbbbefeccggebddhhcfhbdgheedfceeeffgcdcefacbbgeafgfeaadhehdbchfgfcehfgddgfehdbhbhefheahaacbcbgagbffgdabcggbbhbcgfagcafcahecacdhdaecdfdfdbheaahhfhfhhccabgcbafaeffgbcbgfdfbdfacdhhchbehccbedhehebffdgeabbcfhchcchebabaddbhgadfffccabgbcadhhfhbhgfaggabccaaceghbacbbaceafdhdcacagdhedagfbhaffhgfbhhccdchgccbcfbaaafdbdbccbhhaffceeeghggfaagdfadfaabbecdgdcgdhdfehbcgaadabcdgchechfedhhcccafbddfceaaeadfbfaahhechbgcafechehbhcgbhgbdhfaacbacaeehfccfhghhdhacbgeaffeeceefffhgbdfhfheegedbdddechfhfbdhfhededbgggfdgbaefdfahafbacafddeacbdheefddcgbdgfbccbbcgccachdfeehfhgbedehfdabbfcdhdebcgecadgfhcfebdgfhceefefhbhcadhcffghgbfdbhafbedgdgdhdhfcbefbhedebbehdbdebdbchfacddcgdhbedgfdcbhdcddffgbgbdabaaddefbhecdaaadcbcgegbbdhdbagbbgbfbfccehfhhfacabegfchhfgcggahagbfhghbdggcfecheeecbgbaehccfccfadchbcbeahhgdbfhfbbhachebcgheaefdhefbfbbfahacfahgbggegcfabeebbbfagcbddcaecbghbffceegcgechagbbagbgacbdfchhdfgeddghhfbgbdfbbgdbeehehbaedhdgfbcaeahefacgdhaegdgchfhgghcbgfhdgbddcchhcbgfagcgbabafahehbffhfbfgeaahhabaghbebhfbafgaechgafffgcdcdebceddccegdddeeaceffedfbachcfbfbdafgdhahfdcahgbbdgghbdabfhddabedbcbebbdhefhdeafhgdghhgaefehffebggcchefgacgeggbffededbfagbhegdfebhgbddheffaeebbbfffbgcbfdabbegfffdgbggfedfahgbadggefafcegdfcbdhggghfeebhbbhhchdbfhggfacddhfececbccggghgaafhcecdccbahbccebhaeddfgfdedccdchdeefaghbggdaahbhafddcbaffdhahbhcgdhgbhhhfchgcbfcgafbbfghaghhhgbfcbddaddffcdhdbbcbgdddbcehbdhhfebgafgdadachagababadedeghehddhahaghfecfhdagdggegaebeafdhbccebcecadhegfebfcedbabbfcffhaebdhfebbgcfggddceafadgaehfgecffhgageehfdbcbafecbehbhfcdehbbcggbfghbcggfabgagccagcbfhdaedbffadgfbfgddebdfhdecgeaafghbgdeaabadhfeedahhbdfagbcefdecbedhhhhaahdheadhadhbgebefebchfeabahbhhbagehdedcegbfefhacdbechbcabbbaacahhacddeabgffdefghhcbgddgefaffcfebfgfadfbbcgehecgdfabadhfahcgchcdfbafefhfafbhbefebffbbfgbeahgaccfdcchabeahfhabefcccedhceedecdgeabhcaheehdbgddcafedbhceeghabcgfcheehdadcdeahhdhfhcghfcddbdedbcfagchccceggffgaedhhbgeebhfeebfggfeaegdgdbfagdacghbhgfdhfbebcbhahdbdcecffhfdcffaehhcedcbegcghbggfhchdeeadbdfgbfcaefehhgdfabecadhhfgdbcdedhbbagdacaechcfedhbfheegbcbcefghehaefdeheabddhaggbdffhdgbfafcgegfecchgbdgdhbchhaacffbadcfdhhbdfghhahfbceebfgafgahdfbeadbddbeggcggcfdehhabfhbcfcbbhcfaggdbhahgcfefchbchbdeaeggghhgcegacbbcbaaegebadcccdfgececaebggfeghghbhhbdffegbgadcgcgagaacbhagdgfbfhbfaecgbahhbcbhehhdhhfagggceedcdehdbbbccabdddchcbccaachgbbcfeeabddcffehffcaaeadfcffcheaafdfchfddbfagbhdgbehfeccghhbgebhbeedecghddhbegedhaceeegddfebbfadcfgghffcaedfchabacfegdhbadccbdfdadbhagbbcegedgfdacagfhhfdbheeeheaadagebaaheefbhfdhdahcfcefgabffbfacdfddfdhbaabgdabdheabafhahefabgcedghabgcbgdhbdbedffefcefbadccbegecgedegfdbeeffbacgehaafcbaedbabfdhbgeadhbadgfegacdhddefeebhfbbceaedeegdfgheedcegfdbbagfehfcagefgaadeggcffgbbafhgaahageffbhfhdcgecbabhcgfahgbefhefgfdccaebfdeabaccbdcdbheaffecebhcgceacabhefhfgcahfcchbghgdeahfhbdbgddgeccbcaheagbcbadhabdebcbaeebcheadgdeadeedcgfdgadgbgccadcehdgghhbfcggfccaeafahfdfgbaabdcgdfebeddbfbhcdcchchhbechcdhcfcedfbhhfdchadgdgaffdffebhdedcgafddcecbcfdbgghbeagcddhhfgdbbfhbccefhhgbecccabdfbchefgecehdgedhhfeeedcfhehcfbfcchbhfhdhdcdbggbfdfbaaefhafbfghhagahdhcddegedefahcchcgfcgcdeacdabeaedchghfdcbacbdeafcfhbhdfhfaageadaccgbabdbcgcfcdcfacgafdhcdhbaheacggdgahacfchhfbegdcgaffdbfebeabgghcfhbfbghaffccdfebgcgbddfeaffgdeaaebffhfgfcahffdgdfeeaabeagbgcghccaahafffhfeedhcgfgdfgecgddffbehdehdeeabdgfhbfbhcachghbfcfchgggccgfhcfagdgfedhefhgeffgchdegbcfdfdaefgedbcbgfacchahegfhfadebgbfdefhbddffggddgfgfffbdcabcefdcgafcgedbhagfgbbeghbeedhgdaahfdbdegfccbdcbchadaechggdbfbegbedffhbeedgfgahaaheadgabedcbfhhgdddaceeghdegddgdccefaehehbgeafddagecdabcdfahahccbghccggcaegacbecaafdagfedgddfffgeeagdhaddhdfahaahfdadbeghhbeegcacdhfchafgedhddhdadddehbdgchcabdcecagbaeaehhacgdcbgfffgadahfabacfcceedaehhdhbbcddaaafgbagaggbgahbddfgdbfcefdfhgaagbfecgcceaecadddgabbbhdfegddeddcebgghabdaffaabegbfhdecaaadeehhgdaechedceaaeabagcgffchgdhbhdagbehfggbbbfbbbbccheaeccdafcbefcdggcdeaefbbgccheegbecdhfdehebegecegfagbfacdcechbaafcdehgbgcccbgefebgccdcehfbbecceheheeffchhfafbgbdedfhgcgddahfcdegcachffgechbdfcgbgeaeghhbhggbbchddccahafbhgeebdfhhgdffcgeaefbgeebggcfghggfdcggaffgacdcahceedcahehfgeefdccgebeegbchdfbdeehahbbhfaedeaahcdfhebdccgbfddaahhagbbfgbccgccfffdebehehffebafbhebgfddeefgcaaafgdbhhadggbdhbaabebhcecgbaedaedfcggcggfeeghdahdbefagbceccagcebhhafbgegcafcefbhgfegdgahadhgfeafdaceggcahhcdeeccbhaffbefeeebaegdebhchbcgbfbfbeacdahabeffabhaffdbgcdgdgeedgceccgfcgfeccbceacbgfdehgccehhhfbdhdcefabbcddehdgbbdegccaehhdgeecdhehfeaggebcdfaegdaefdfbcefabbcebgegceeaagcedcabfbgcedeghbgacbfdhbbcfgcgefchhcafdghhbdfbeebhfgcehegfcbdggfffhfcdeccffagceabbgdfghedbfghddeaccdfgfadcaceecffabcgagbcdhbgcghfaccghcbbcdggfddgegefeghafagagffghhegcgaebgdhbgfgebdbhcbfchfbfchebeddcdadbdccbhagbdhafafahcbeeabgeebghbcaeecgedefgdfeddecffhcfaacebaddcdhhffdabahefdhahcgebabbadfbeaegdefababdaahgdhgcbegcehdedaghacfdgddadedeecchbabcfhebhhgchebhggcfbgffcabhcdgedagahdcgcaacebbcaehbcegeehdhccdgcbgbeaahaabecchcggdadcfhbagecbcedaghbggbghgacfcadgbgaggbgefbghfbadabbhcagaaafdbbbchbafcgcahahfbhabacadchdchbfacgcbhchcbbcabbfcbgdbaeecdaecbcddafeaadcbeebffhhgfdafhehcedeffhagffgfaagfehcbgcadfaaeehgbdcgachgheeeeecbabecagcddcehgdfhghghbffabcefgghhadbabddefhdddadbhbabggbhagegedfeggehbadghgccgfeggehecadcghbddghbfebgeefddhgbechcgggbhbdfaeaddafaeggacddfcbhgdgacfgdehgbadcdgcagggegbabgcdfbgebabadfhcghfaddcdbacfgdfabadhbbdccecfbchhbeaehcaadcgbfdbgdefegahaebffdfffbfbbhbbcdheadfhgcedafcabdfhhceeebffahgdcghdbechggcgdegfaeehgadcbahbhgecedffahegfhfbddgdhccgcfadgaefgbhceehedddbcacgdabdcebebbhhbdfheebbbafeeafgaheehghbcafdbeddaaceeeffedcadhhehdagbhadhfhaccdccgggceeghghcfggebgddfdgeaffchaebgdaahehgcgaheheffhadchhceefefbfdefedbdbdbcdfbhcggdbacbcgfhccbagffcbhfccgefdfefecafccgfbeedgfdedbgeadgcbdaeaecehccbfaggedbdafhdgghgbgadbahbfbgeeafbaehfhaahfhddfcbhaccbcbdhdbdhbbabfhgehgdfggadbccbeedggggbhbaacabhhadgghdefeaggcachdafbggaagacgbcfbfdaehecdeabhadgdddecbecheefggchefhaeechadahddfhhadbbadaehfcghccfbcbffbgabfdfdcedgffgafchdffchhhacbghcehdbcaefeadbfbbcdbfagahghaaaghccggdagafdaaefbghfhfffffdefdfdchfafabeaghahdfabffacdghabdffaahafaffbbghaggeehfbegdhechffecgecgbcdhdffcfdbbhahaefdebfdgdabbedhgfcfahccffdgfdffacbedghcbhdcegbcdehddbfagbhdeebehcacaaechhedfgfacedffbgecfhgbadacddddhfdhbgehefbaahgbfcdcbcdcfeeahhegehfgfcfbhhchgabdcefdgafdecedbacghheebbgaaaagabbcfgfehdhdfdhgdbecaahccfccfcbfdchbbefahedeacdddhgeafgccaehdfegadhbhebhbedbhgecgcggheabfeaacegchgdhcegdabehabcgdaedfeecafccbaebghabdgeehbdhcfffgbadfffgchadhfegeehacdecehbgfhedaeggbdedcehbbdhgaggcccegbgfgfbbffhdhchceebgfffdfebhgdeefcbdhcfeaeahhhbdddbbahefdgebbafgchcbbhgbdgacfcgbfhcfggcbegcghaebhgdafbcbhcdeebfbbhghgabchdagdfhcdcdbdfcchfhehefaeehceaedefbhcbcfdfghcabbgafffdfbheddfhhbeaagbcefhcebdfdbgagdddechhgegffdfgbhafeaaabdfeedfcgafcdebbbaggddeecfcgfcggfedbhadgaaadecefccefgabafdhcffbcbedbegheghadbeadheaffcfcfefdcgfdcbeghdcgdcbehbaggaddcafafcdhaaccbhabcdhffacebcchcfcfgafdcacdaefcdgdgbcdgcfddhfdcdfhbfeeaegdecagggbehdhgffbbegegbbfchbghfecchcafbcbafagdfhecgaahbgcahahffbheehbfbcfhcecadgcbgcbhadaadhfabeefdfcfhhecdgcheeacgbbhebhabeacafhdcbacaeeecgdgcdaafchbdgbeccgchfgbggdhdhdffgehbeagghacgbgadfdccbebhhachdaebeecaebhdbbbchcgefahgeafeaaddaheedgehhddaeedegbadbhbghhchhfchegdafhhedcfhhadfbebcdcadbccahfhedceacdffgcefcacdedfhggchafaachefcageddbbffghfbcbehbcfdcgacgcbcadcghfbahggffdghfdggfebhccbaedcegecgbdgabeggaeffhedfaeecggcdbehhacfbfechaafaedfehabhffbdddgehgehabaffcegccghfedeeedbbeffhdbgbffbhfheadccfbbcfegbabdcfahedacfghgfffbfbehgfbbcfhdgbgagghdchfhfffccdeheagcfhdhfdcdebdchcfbbdahagbcbfbffhhchdbegehcfceeecgffgefeghfdacbhcdgffcdbbfgdbchdafahbfdhebdedeefhccefffgcdcegbhggafafbhcccgfgcdgffccdaafdcbbebacbfcggcaaehgdbbbggdabdbhhdaahbaccgebegbfdadgcehaccbegcdffdfffghhedaaccffcadeecfhegdcaghfbfcgdbghfghhafedfhhcbebfceacchadeccheagbggahdecadbcegdbahbdbbdfffhfbhdcfbceeggfbahfgdhgcabebebhcaedhhgebabfhhcahcgfffehffdhcegeechdbfacgbafacfaedfbabbghefbbdfffebgcbbacbfcdccagabgbceahbbaegfbdgafhbfbccefegfcghbabfaahcadagfdefaegffahbfeadggchgdfheebehbcefhbfdhdahccfgcafacehfbgbfhgfaabfhddccgdcafhhhhehbaggceahdgeeggbgbeadcdfdaechdghegfdacdafbebhcdfdhghcbefcbhbefabdgeeahefaahhdcfgbdfdecagdhaheaaageegdaedadddfacgdhchbcgecgeggegfbcdechadcdghdaggaafbcdgebcdagbfheaegaebchaccaaaaafccbahccccadhahaegaahchhebaebaegchhcgceaefdefdebbebagaadbahcaeaddafbccbghecehgfacgbbgbehbdbbhbecbcddeecdbehadebfccgadchegaffbcadedgaaadbfcbagcfaeeahghdehbcadcdhfchfccgheahccfchbcghbceadgagaeffgedagbacbheeegdfabfbdbbghbehfbedfhedbefcdbgahbfhdcagdbfcdbbadgeafaegebbhdhhcbfcehccdehfhbhhefdecdabhcchfbghcdbgdebgaadhbcgfhcccfcdfefebgcbbgchbgahgbcfcfeaegcgdebabgecfhdgfgfgegfdhhabeebbcdhgabgbhddechchfafbgcefbfggbahedgcdhaehdadfhgeegbfedcbfhhdahcedaggahdhcdcacaegggdcbfdgedbfcdbfeaeehhdbcfbeggceefhfdcehffeabgffgbbfaegcbaghgaecgdhbfdadbfdcdahbcagceeffedfcebeceedbhdeaahcdabecbcefhbddfagbbcdfggggbdgccbfccceeebbdcehhefafhdcgbbedecfgdcbgefcbgdebadaeabcaeeggfcbbegaaabgfgagfdcgdggaghcgegecegdfdbfdbgbgfbecehaafgadgcccageefhcaahdbgeadfefbdfbadbebdgdeehabgcbgceaaaadfeahafaaacecfcfbhfcadeccggcghcbegbdggehhgdbdggffdhfhdhbcgdaffcbddfccbbbhecccahhegfdceeechehegbhcgbehcfghhabhabdgggaccefbbefhffbdgfcbcaabbbbbcehadadfeahfeefcbgfaeabgababcbcffcfacaggafefbbhdheddeecffcghdbeadcbfchddehafahaadddahffehdeceadhceefdaahhaeahfacadcabheadadhbghdcdafdaedaadhfdcggeghecahddgebfhdbaaeaehbecacfcaehgddadcdgahhghchhcdhgdadfbfddfhcdcfdghheagegfgfebaehdecbfhebeddhfbddacaaaeggcdcdegdhdfaafebbhfbfgeaggahgefehbhcfffeadfbabcbbhcgfggeehdddahcbgfgecdefaffbahchbafahbegehbehegfbebdhgbhdgbdfddheahdbdbfdcbcghhhebddhedccegahbhdbggcbhhecagaagaehdhghcabggbghabagacahbebcdccbcgaffgeagfgfheehgfgghgfbchdfbfgddgaaeeadbhaadeabbghbefcgefefccafbaffegaffagafgcgebhagbgcgchafhfghdddbebgehgbfaabchbabhdhccahcffbaafbeghbfgccgcdacebddecfgceaabcachcgfbhchcegehggdhbgdeecgacgcehedbcaccccegaafghagahbeddddgbfcabgbegegbgchgcfebfcceeghhbdfdaadcgfgebefhgffacbcheeeacdhegfhhfcbdhhhadfhbcebegddchhccdbgbgfadhbghaghddhefdgbbbedbefdhhbafgbbfchedfegaddfgbgacdddhbggahgffhgdcghfdddeggbfhafcdafcbeabdghbgfeaddfhhadfhecgehahagbbcbdfacgghcgdgdcfdfccbfbgebfehhgbabhadfgcaefghhddeffgcgehabdhabbbcabffaafefdefghbeehgddfdfbcfcdgfdacbacgeacafahgeegdhbacgbeeeacbdcdecgdhgfhdfhbcdhfcbfehhaddageeahadfdcdabggaaadhffacbabcdecbagcahffchbdahbbhbehgchadhcfdgaehgghfdeacfddfeeefaddcddgcfdfedcdcacheghgecbbgffdgbgaecgghcedfgghgahchgbdbcehabdgcbggdffdhbgehfeffdaebbhcddcdffbhgagcfdfeedadaeaghacbbcdfffaccccbcadhdadhddceacchdeaegebebcgeeafgaafdaacddehdhbdcgdgehaabchfghceacbdcbgfecfabgddegcbgcbheaecaggaahdcabheeeefdhbhgdaefcdbchdcfbcfaghahgeddbbgacfgfgccafdcegfbhhghffhfedahebffdcdaagcadfdadabchabffacbecaaeffhabaahcbcaecdeegdehabacdefdebbcabdabcdcedghgcdeghegaebdaghehaghbbacddfagdhegcbebfcbbdfbbefaeeaffahbdebbaafgcgcddeeeabfbfdcbhcgecgffcggcgdaaccdfhachbhahccabehggfddhcbcafcbhfeeeegdggdfagfcceabbdebfgdgdfhccdggafbgdfdddaffffggbdhgbceeadgchebhbcfehaacafafdgeebdccghggceabbbacefhdfhggegdhehdgdgabfhhhdhbebbhfhgaefgcbegbbfehachbhgahcaagbbfgadgfafhcbfdcdhbdcbfbhfabfaagcfecbdhbahdbegehgfdagabgfchdchbefghgbghbfdccbgbheehcebacdaffhgceebcfhcgffbhghagdffgbggdbgahghbcdcfbbhhgeafcagaddgbeeaaggafehghdaeebddahefbedchgabdebdchdhedfdgfhchcfhbbecfaefgegbbhedgadcdafbgedfgaehcachagehdcaebfhafccadabbeegdeccgcegddccgfccghbgeebehbfafbgagadechcfcfhacccabehgaachbahgbfhhfcehbgfedeefghgadfgdfacgabecgdbdffchehdhehfcgdcbaaefbgdbhhdfdfaacdhgccggcdbagdcgegdffggefccahcbbfaaadggfbhfhdhfhgaedgchdebedeffbffbadafehddccabaafdgadbeefaacfcacdafdgbdbefdeheeehcecdbhbbhdgbdafefacgddcbggaccecebehcdaddebehbbdgcfefagghegbgddceabgdcbggcdfdebbggfehdcghbhfedhadaggchfabageehfdfchefbceccbgfagaaegddddedbaaafdghccedfaghbeebdechcfdgahbcabcfeafgdbcacahdedfhhhhbechebbgbcbhhbefefhehhddegadfhchdeghghghchgbacgfagbhffcbdcfbbhaeegecgcbababbchgcfacdfeeahbbabbffabhgdageahfdgefeehhbedbdfddgeadebccecaadhgggcdcgdbhheacbdfhagcehehehhechcafedhcgabfechgffffdaccebgdadfhffecbdehdgfaaegfbddedfhagfdgabgggcahgehbcebcahacddggafggdceddcbbfbbdgaeaegdefdgagfhgcfefhabcdceaefdcfhcbfffdaedgbcedaabhbcceegeadhcagfbecghdccbdfghfgaehcgdgehhhgbhfgabbhaebcffhdeecebbghfeeedddfdaddbecbaedgbdbfhdbafhacdeghhbecbhgceadeehcfcecbhdceccgggfffgbaaagceggbdfdahhdahgcdbechcheaffaffgacegdhdgacgdcfbfacbcbebfehceeacecgcfgfdghbbcgchhfabgedeacgegggdafffddbbcccebedabebaaeebgcffbeabbfheaafdchhddddfhffhbbaadgfecfgdcfhdfeghdfdgagdhdahfbhfffcbhhhcbebebfcbaaehaccagdhdegabecddbcgchhhafbbfbfecahcgcbbghbadddheffgeeffbhghaedcececefddfedahghddebabhfcgdbghfbdhffedahaecadaagdeadfhaafebddgehgcecffbfbdffdfdgcdchcchhgbdchhbfbfhgcadedbbggefaahacbhcaafcaedfgafedfahbbahheeaedahfhbfaghaccfaccffafebgeafbfffafefffcfdbfgdcggfddfaaggegefdbdehhbefebafggbafhfaccbcahhhdecfhgehaaeebebhdchabfaehbgabfhecbbbafaafeegbffeafebcefbgebhbaddcffccfcacggddehdbdfdhcefggeagadafachgehacgdgccbdfggebcchaghhgdhddcdbgcbbaehcgafdhdaagchgahfhcfcfhfhfaagaffddgahfehfcbeabdgafdddcachacgbhdedbecgabdccadddbebeheghgfaadbahfdabfhcgceachdgahhegdcgbagbdhbceedfbchheehhddfeceabhdhadfbgedbahefbgfacbabedgafcbgbefbhcdfggggfcegabhdchegcdhhfaghedadgdaebhdhbhfcaefcdbafehfchdbdgbgefhbggefhddbdhgfdafaeffgeahahbgdgfeedacddfegeddhdbahgfgcgfcfgbaegfbcfdfbabheedeheehcbfehchebaffgcgahbfabhagddcdhgcbhhfhbedceaadcgdcabcbachdfbgehafhhdgbhbdecdheccgcdbddddhbeffegddfgbgfccbefabhdhbgafceabfegcaefdcdeabhccdadehgebeeggaghfcgadcfgebdfcchefhhchfgaccgadeaaggabagafhdcbfbfcbfeaccaefgfacfaadbcdhcagfchceeefbbfedfaadfafcbffchbbbbhgegaacffegcabhaccgchadegfehgfafeedeegbbchdcbccdeafdbbahgegfbgcfdgchedbgdeaehchddehefhdedbbehdccbecfhddchdgggfcbcbfhaaddbehaabdbffhfachhgggedaffbcfbcaedfddffggcdfhdahdgfbcabhgcbddddhgacbfhaecdbbhbachfdbgeaegbhbecacdceaceeehgfghgahddabhbffceghhgbcbfcdbhhbfehecadgdehdffahbhgafacgffbheaabfhfhhbfdffgccgbdfaedagbfddehdeaaegadhfgecegedhaahedhcffgabfdggeceefdbeheafadeaeeehdheafeccaaaeceahhbdgfedghagdeddhchahecbeccaegadgbhehdafcadgegbdaadhefbahdadbahhcgebbegdebbaacdadhahebaeeahfbgfdebeffcbbdcbdfeeadehafhebadgbcdegeaebcfcfhdbeafedbedgdhhddfefbadfahhcebaefbafgfahbefedeagbedcfhafghadaahfbhchedgfhdcchcbageddddbccbfcbeacdcbafhfechhbbabaeedahecbfhegdeaggbgeaeacdhdfhffebaebfgccfgbacbgbdffdbfgefbbeggaahebecdghchhebgfedcheafafhcbfacfhggdbccaebaacgggbagfadffchhaabfhhedagfbcgbcbhahabffbbchdcgdchbbgfehdbafabhbaaaabgfchhbcbhgdghffebehdeedfdefdefecchbbaedacggbddffheadadadhfhdcdgechgddbdfhbgdfdaehaahdadcgcfafdfadddgegedhcgeggbfgbfbbadhcbahefhhacgeachaegecefadgfeafahhbhgfegfeadabfabbgfecdefbbcbgcbfdadafbfbcacdfcehabdcehagachgeadhbghgafhcfbfddbcdcfghegfeaeceffdgdcedhdfffcaadceghcfdachagbedghbbbffbbcggfggaacghedcefbeecahahbbbggchbafggegggffdahhgaeccebcecdfbchadhgbfchdaeadfhddhhfbdgdhbgecadcdcaehcecdacgfbbaaafbeeedfdahddbhgcdfehahacgfehgeadgehchefhdbdfabhdgddgddbbafagbachebceghdbaggahfegbheecffccfbegddcefgcfcefacgaacgbbcfdacfchggfbcaghgaeaecbhabhchadbfgbhdegccedeebeccadgcefcfeeeehfbfhabdhdfdgchagbcgeabagdfcabhhhafgbgbabgdhachgdbfacgaabgcbhbbgcgedefdfegeeaeddfadhgehhccbbdcafaeaecdbgbfcbbffhfagdegdgaeadgabgebcgfdegahacefbcfhfcfaafeabcacafdcdafahghhadebfbaddgdedaeecfgdccffcdfbbeabaecfgcabaefeecaghhbbbhgdcefdafeacggaagbbchfgbffaegbffhbhdgcedgefecffbhgdgdchahhffacdhdcdbfhfddcagafhhdcfgeegdddbdgecbgfddeahachgcefbhhgfecdhfhaafedgdabgfbffeedgaaahhgedbadghdheaccdcebhfhebdhaehadhgachafghbfdbhfebbfbhefaafaeeahdhhgghdegebbfahbcahdhdaadfahcbhfagdgghdedegbffchfbcffcfaafacghhgfdfdcaafeggbdbaaccfhfcafaahghgfebcadcabgghabaabddhcabcfbceabcfgehghbgaheahfaagddfgdhaaadeaegfcceacfgcfccehdegghdeccfcdagdefbhhfhbdgeaageabbgaabedebfhbecgbdfabececgedeadgbbgcccfgecffgadhdaaefcahaeceffcggaabdfhhafegfagaagffaffachehfhfdhgecdebdbgcggagggdegbbgdaccfbhbbffdbbfecdgabghhecdcdeagfdaceadffbbgcgdfbbfcaebehfhcbhbgcbbhbeehfffadafeccgchaggffagfbfhdggecddaabaebfadhhfgheeebfcgghgbfegahbaacaeefehedfdcbhgcebbdahegdcgdegdgghcddchhhcbacacgbdbbcghgafbededbdfeghefgghgahbhaeabhgbfhggdccgdfeaddebccaadhbchgcafbbcaaadcccfhgfcbbddedehcfbbddcaedcedcafecddaagbcbfgfbfhggbcbdcggfcchcheechedfgfhddeeadcgeehhhfgeaadchhhchdfebcdefhafdddhhchgafcafgcefbgefdbgfedcedhhgcggffefchfhfhecbchggaedehgadfhbaghfdecgdhfagbchebfcbcfgbdgebggbefghbafehdefehfaaccceaagdgceeafagdahdfecaaafhffahaceaccdaeaffffdbfcedghdhhageggdgahgcbbdgbadhfgadaeghdbgccegadcgdbegdfbbhbeggcgbcchbgbhadehdhbbccfafcbgbcchbefchacagdaggefbdgcfbhggbhfdchcdeafdahdgcdeahcbcadabcgaeffhhebcabadbhhhcceccgeegheaccagaffhbgccacfbbebdhfgbdcfbbcbdebbeggeafgcfahgbehfdedehfbbgdccaedeccachgeegecaacfdgahgfahdebfefbaadbcchhggdagdcdgbdfhafgdbhbffcgffhhhggfebfceafcbahaafgegffechchebhdhfaehfgdfeggefgfcebbcgfefhebadehaedhbcdhgbfcgehbaaccghhdgdeggafgebggdbfbccdagdbhddbccafadcgbceahfgfahcbbeebdhdcdgdfbecbheabhebgbhdbgfchbgaegdgbccgdgaeffegeahcbgfcecedddeabhgcbaaegabeffcbgcdhaacfcgagbegceeeffecdfdhcacegehgeaabcgcaaggccdhaadcdafddffhebgcfgchbabbahadcdccdfeggbbbggachgeffgeghfhhehcgceafceeaffbeebgdhdaebecabcagbceehfbbbfbhdcdhdbccedhghbgbdghfbdbaacbcacbdeechfebchaahcgaffhcgcdgdghfgbgbfcdehhfbhgbgaagfffadhdbcbahhbfaghdchdhacfcafcgdhddccgdfadehecacbdeagdbabdagfgbebegedbbdefcahccbggbebcfcffbcecgfhebcfcfbahbhcdaabcedebfchgedbdaahccfehgegaeadeafgfadgfffebafebfedhbhgheehafdefadcagbfdgbehgbadfdcgcafgffgcadhagcaedfhbhdafeabbddhgefebcddcgcceecahhhbgcbehcfafaadefafhdabbddfhffheeadgbhfdegbegebdegchhdacgfbdcahgacfcbcffagcgddbhbdhaghcefehhehgfbdhdfeagdcegfgfhbehaecebgeacdghebghhdafgcbeahbhbggbcafdgbdbecabdhaccahadbedafcbdacfbaahbeaggbhbahecadcdeggfdaghabebbfbcbbahchacheehagceeabaaahabdccadebefahebbdfgcfeecbedbedafedhgecdfgagfehhaefccbhecdhdaddfhhegdgbaebgcffbfcgaehhacchfccbhcadadbbdgccahhbfbhffgefagfgbhhabhebcfcfdehdehebadggccdcaaabahcbggdadfghcfcgehhfcfdehghhhhbhhdafbdgebeddbgbgfadhfgeeedddcecbhdhagffhbaccgdaddddabhegcabeeegehfefcbfdchfadgegbhhdgdbadceagcefhadbcaeehcecaabbhaefdffhachgedeedhffhcbgegbegcfgccdfhbehddghgcdcbbhadbghhhdfbaddchbcafbdbhchbgbchbcccbbbaegcecfhbgbbecefcgedeggdhafbbgcccaehcbgdaheebabdhfhddfhcfedhdfbfgfeagcegbacdbdgabfdecchahchcaahgfegdgccadedeabebhhfbcebbhadhacffgdbfgdfbhafhbbaaagcccddbegaebfchbdehgbafbffdgfdgdfbgbehfdabefddggafebfcdchgaebhahagaeffhfgddchbahhfaehdhgbhcdgccgacdghcdfgghfaaehfedeaccbceeahghhacfhebfchehhedgbacfaehbgeghdegcfaaeebbhaggaccgecabcfbddfbcagacdachfdbeehcebecfgdhaaaedffgfdghghcgefhabgcfhhaffdegdecgbhegddfbchhgfgggeaeehebfhfdcbfacefahafbcfaachgadgehgaadhfgbgdcahhahhgabdabfhhfdfccdcdgcaedhhfhheagdggebgfggedbcfdfagechafgadfhhffdddhebfchbgaddebdcffbfdhfgfefcbageacgfffgdgcgcdceahgfcfdachgfbgdfgfddcbcfheebhgfhfdeabhadhgaafdfdbbhdcbbbffcedhdadhaehbhghageddaeehagabhfgbbbbebedcacdhachghdchhgghfgaedggehhabddddggcgacfhfhgefeeccehfdfbcebdhfgcdeebfggedfdadhefcaehdbbgfcbehagcedebbcgfabfdabacbfcfgddefeafehhbcdcdgaagbfbcgbeaggffbabhebebadcchegffgdgeeacffcedhbfhceedafedhgcdehadchhghbeeeaadbfddbhgbecedbhgfghabghhfbdcfdcaehdhacgbgafbbeahdhhefhdcahefcgfhfbgfdegcfedgadfdcfhhedcecgbefgdchcadggfdcacdehggeggabaedgfhdedgdfggdedhhebcaaagfgefheccdhcgdfehccffhbegffafgaddhaagecbhcdgfacecfchedecabcfhcacbadaffbehecfefbgcdfggbagdcdceefgeagbfhgfdachfdfhhcffefehhhbedgcagabehhbcadbfggffacdeahdhgfdcdfccfdgedhgdchaaffggabcaaghgddagacagggcbfbehaeagcgechgchebfheggfagdgffhcgdchacfcabehhggehddebbbcaeafbahadbhddefdfbcehaaheedffehfaacbacbddahheecbgfgffgebchhadgfdgafgcgcfhbedfhfdedbbbfdefceaabehbbfdhhbgafcgehbacccdafhfhdfhfbggceccddaeaccfbdfdghhgegddcadhcbfefhgbchfdbhadcfgaffgbebfgcafebcahchaegfhhehcgfbhcgfdchaabaffcafbcebgcggccfeacfheefageahfbecdehegeffgddafaffdcfhgchfgaedbafefeadafahadhfeechhhgfbgchggchhhdeedheaadaddfhhhgghfeadgabfcaecdagghcghggdbdcacbhbgdcbbccgeccgfcedchbbfhegchgeafggaahccbagddfafbdhaebfdfdfecbehhcahbcbccaffffdgachedehbaefcgcbfebfgdgagggdddgcebbaefaffedhcfbabcfhgdaecghfbghfhagdggbdcedfbefcgccefcahaafbgehfffaddbgffbcgfhbebdahfbgfbdghafefceafggddafcffdbggcfddeaehgdhehegdeebdhfdehabccaaefdhbddbbgafffeabacehhhdgafacfagcdfegafhgffdcbdebfaaeadcaaccfcaaffedfbddgagbbbfchfcdffgfgahddhdaehebahehhcaaefcdcegabefhffdaegabgecgdhfcbfcfceafahfcdcbaheaedbfbfhhbgfdacgffcgcdfhfabgbbdbfgcchabgbadeagcfdfdfaaefbfdcggddegfdghchhfdhdgegdaddahabfdddchhgfecddeccbfbfdgdgghbggbadfdhhcgfhchcgdeafcccfafegefedhegeafdcdacgaeedbeadgcagaeeecbhbfgffdaahacfagbehfecehdchhhdbadcfbhdehddafaadbedhbfdaafhaecbefecgdfddagdfhdaaadhbbcbbaabecdbahdgcabfaaafhefhebhfcbgdbgfgaahahchbcahcahhhdehhfgehhcdbaahbagbhaaacbhebhdbchacfggefbhgbhfchdegdehffgbhfeaaeacbgafdbfcdehfedbcggbedafcfccfgchhaaeebbgegfccadehbgdfgahdccbaeahfaebcfhgdeaffecefahcghcbceccadcfdggfdfehceehagdggcaebcgdgaghdaehgdebaaacffbfdedcgegagedffbeabahhdebeebgbgahcecedgcdfhgceagebgebcacgedegcefebhaegchdbffffdchbgadgcbcfgahcfddfdhdggghedfbghahfaddcefacghfddaagadegbecebecaecfffahbfhedhbhcbhabdfaebcbcgdcdfhachheehaagbhacgaebfeggghafccaabacahgfggfeheeccfgecccbabbfdefdffggfedddaaceeegbcceeefffgcbcaeafcgchbgcbgefcbdedgaacffadhbghfgfaehhffbgdfdgggccecchhhhcgaagfgdfccehaffddabbhdddffceebhdbhbhgeeagbaggfcbgddfhgaeedbaeadgheffabghcgfbdhcbdfgcehgachagheehabebdcafafgefbfageccdacfaddhhaghbdaefacggacdbhdadfcgffdfahfhhdgaghfehhcfheabddbhadfgabdaaahheghcfegedacdeceagfhgaeebfabfabeeheheafaegchcfdcdabbaggbdgdbgefddbchchhgfcfahaccaedacbcfhfggbebefddhccfaecadccfcgbdacfgcceadabhgecfgedgbfgeabcchdfafcghechhdagbeagdfbbghachbebahhafbgegbefeeefbedebffhefcdggehgdhdfghdhdadaeabbdfcacceaehgcefahfdeddhcgafgefhfaeabhcfhgffabdbaaefdhefgecebheghagahagggdehehaehebceghccbgdacchdaacbgbhbfgfegbdddfhbebdfhhfcbefbehccacdfaabhcecfbbgfcbcbahdbeadaafdahggahhhbebgfcedefffgfbhbbcbbaechdahchgddhbbbfefcbdageahfcbhcfbcabbcaafehgfbdbggcbgbfgadbbcdhdfhehcehhaggfhbgghbhgcfecafecbdfgcbfefeegdcdcdcaddabfffhfddhegecbfafcebahdechgccbcdghafedbdhhhcaecghghhgddacbcecfhaehgbdhecgeehagfhfehdhcdbeffgcehhefaheebcagbbegabdhecchegfbehgdgcagbedchdaaefhfgcedegcaehcbhaefcfedbhfacgbhdaebcaeghhhdgbefbbddghghgdaabbhebdgdecbdbagabdfceafchdbfhbgacffdbdgffaahaghcbeeffchefbcecafffcagfhdchdbhcabdfgbcaagfbaceahbgbbegaaahdchfcabhgcbgcaeeagabfbhgcdeddechgbebcfaahchccdgcbgdghcebgaebehadafeccedcgceafcdgagehbaahafaeebhegdhaaccgeghbachaadhbdaadfbhbchfaceacgdbcbadcccccfceacedhfdahcfhecahadadeaggcbbegdahffcecfechbbedbdeedhbdfhfgabfdceahgebeaddcfhfgcbdfaeagdfeehbhbfaaeebaffdhcdeafgddghdedbbhacgbagbedceahhhbcdcabfdafgeahfhhafaaebeheahdhgfcbhcdefdbdhbdfacfgdfcebbabaeagbchaecebfgffhacachgfeacfbcgbgghhbghfbehgcedbefbgeheahgfaadbhcagdhgaachgedcfhhhgegcegacgafahhagchedhgcgcgahfhgddffadfcbghbfhcdbbhebfhhhfhhcgfgccdcfbehhdaeccaeehaffheeeddhbbfddafbbbaafafhdfdheeebdagadbheceagefhghhgehddcahbfdfggfegagffabfggcfebecfegbggaaddfcbdgadefafhfdfabbbfdhbbaaaaaddffeaeeeacefbcbgcchdhccbecbecbhfgfchbgdbahhbbahdcghbbbcfedbgeaedfgcgefafehgghgbbeacfcfcgadefeaabgcadhaadhgbgedhbdbgfgbdheaeaaechgccfccabachffggaheggfbfcbbccfebdgdaafabfcachgaagfgechbebchdhdecchccecebfeeedeebbcfecgadahghdcbfbdhffdgcachdhdeagbeahfdhebghdheecebhhhchcbcbegbchgcgdffhgdhbcdfehgehgggahbbdhcghaafdgddegcgbfdffcbeahcagdbcddaceahhgccdbebccehhgbdgafghbhbedbghbfgaabdbfedhacghdbfehedadeegfcfgheghfbacfdcggafbccfbgabcefabhgagcgghagbfcddaeabgdhhbhadefefecfceeadehebbafbefccabbcbbffgbccdaehefcaehbfhggdeafecggdheaffchbcdagadgecabbghecabhchffgbfdhhcacfaagdhcfhegfdcaddhfcecaghdfhffbdfbbbadghhffdhfgdeefaggggbdfhagcghdhagfhgcebcbhffdcgcaeacafbaddgcgfcedccfgdhadefghdahaabafcaafhddefahhcfggegbbdhahahhabhgdhgbgbedhecghhefecgfgffffeegfdebcccbegeddgbcgghcafhgcedaahggcchfebgahcdcafegddadahcddfdefbchdbehccabedefaaddeehedbhhgcdddfdgghgacgbgbfdcghfcdeggfgfeaahefccdcadegfcacgcafhcaebgbhefhefdchgfbgbffgafaghbdgddcebedfbdcggegebhdcfaaffbdecgcfbfccbfacacbhghdhggcdgcadddhfbcdchffacfcdhdcfcfebegecbfgeafcchfegcbgegbhfebchhhadfefgbddcbfeacahecfaagagdbacahcdfgbdaegcfdggfgfbaccbbchedhgehahegahgfgacbgahffafacgbeffafdeeddabehabfadhhegebgbbbacffhfccbgffghbghcdhfcgbacdheeaehfbgdebecgbbfcheececfcdffgebdefccgafcbbfadgfffcchgeeahcfgggbdddfcdcefdbfghceeegeccadbcahbhaecdbehdbegcbfcdbgahccbdfcfgcgfcchgdefgfbfhccbfdafccadfffddhbaceaahefgbgdaafcfacdcedfcacfecgeeceecababhdchaeeaghccchedbbhdadhcadeaeecdhechahhggbabafecgdfggfbgafhfcbabfdbfcadacdbcafehacfhhgfheeegffhcaahcbccdgefgbcfcedbdbgcfdhdaeddedcgefahdefbghhadcbgdhabcheddhghdafhfghacecadbagdbegbehdeeghdehgfegccfdfbffeggcbhghachegdcgghffebdgeabbbggfeehfeffeheaghdefcbcgcfegfghgegdbccgghddhhdfggbeacggeeddbbcafadgdgfbfaeeaabggcchebfbfaegbgghhcfcacdfdacdadbgg'

    total = sum(map(count_palindromic_borders, gen_substrings(string)))

    print(total % (10 ** 9 + 7))


if __name__ == '__main__':
    main()