## Story

Before we dive into the exercise, I would like to show you why these numbers are so important in computer programming today.

It all goes back to the time of 19th century. Where computers we know today were non-existing. The first ever **computer program** was for the Analytical Engine to compute **Bernoulli numbers**. A woman named Ada Lovelace wrote the very first program. The sad part is the engine was never fully build so her code was never tested. She also predicted the start of **AI** (artificial intelligence).

Computers will be able to compose music by themselves, solve problems (not only numbers) ... So in her honor reproduce what was done back in 1842. The Bernoulli numbers are a sequence of rational numbers with deep connections to number theory. The Swiss mathematician Jakob Bernoulli and the Japanese mathematician Seki Kowa discovered the numbers around the same time at the start of the 18th Century. If you want to read more about her or Bernoulli numbers follow these links:

https://en.wikipedia.org/wiki/Ada_Lovelace

https://en.wikipedia.org/wiki/Bernoulli_number

http://mathworld.wolfram.com/BernoulliNumber.html

## Exercise

Your job is to write a function `bernoulli_number(n)` which outputs the n-th Bernoulli number. The input will always be a non-negative integer so you do not need to worry about exceptions. How you will solve the problem is none of my business but here are some guidelines.  
You can make pascal triangle and then with the basic formula generate all Bernoulli numbers. Look example below.

For the sake of floating numbers, just use `Fractions` so there will be no problems with rounding.


0 = 1 + 2b1 ............................................................... 
  b1 = - 1/2

0 = 1 + 3b1 + 3b2 ...................................................    b2        = 1/6

0 = 1 + 4b1 + 6b2 + 4b3 .......................................  b3 = 0

0 = 1 + 5b1 + 10b2 + 10b3 + 5b4 ...................... b4 = - 1/30

... and so on.

```
bernoulli_number(0) # return 1
bernoulli_number(1) # return Fraction(-1,2) or Rational(-1,2) or "1/2"
bernoulli_number(6) # return Fraction(1,42) or ...
bernoulli_number(42) # return Fraction(1520097643918070802691,1806) or ...
bernoulli_number(22) # return Fraction(854513,138) or ... "854513/138"
```

## Note

See "Sample Tests" to see the return type for each language.

Good luck and happy coding! 

PS: be careful some numbers might exceed `1000`.
If this kata is too hard for you try to solve pascal triangle and something similar to this and then come back :).

Difficulty: interview

Starter code:

def bernoulli_number(n):
	

Solutions:
from fractions import Fraction as frac
def ber():
    res, m = [], 0
    while True:
        res.append(frac(1, m+1))
        for j in range(m, 0, -1):
          res[j-1] = j*(res[j-1] - res[j])
        yield res[0]
        m += 1
def bernoulli_number(n):   
    if n == 1: return Fraction(-1, 2)
    if n % 2 == 1: return 0
    bn2 = [ix for ix in zip(range(n + 2), ber())]
    bn2 = [b for _, b in bn2]
    return bn2[n]

from fractions import Fraction as f
def bernoulli_number(n):
    if n == 1: return f(-1, 2)
    if n % 2 == 1: return 0
    с = [i for i in zip(range(n + 2), consider())]
    с = [b for _, b in с]
    return с[n]
def consider():
    k, t = [], 0
    while True:
        k.append(f(1, t+1))
        for j in range(t, 0, -1):
            k[j-1] = j*(k[j-1] - k[j])
        yield k[0]
        t += 1

import math
from fractions import Fraction
from functools import lru_cache

#cache = {}
@lru_cache(maxsize = 10000)
def bernoulli_number(n):
    #if n in cache: return cache[n]
    if (n == 0): return 1
    if (n == 1): return Fraction(-1,2)
    if (n%2 != 0): return 0
    res = 0
    
    for j in range(n):
        res += -Fraction(1,(n+1)) * Fraction(math.factorial(n+1),math.factorial(j)*math.factorial(n+1-j)) * bernoulli_number(j) 
    
    #cache[n] = res
    return res


from math import factorial as fact
from fractions import Fraction

comb = lambda n, k: fact(n) // fact(k) // fact(n-k)
result = {0:1, 1:Fraction(-1, 2), 2:Fraction(1,6)}

def bernoulli_number(n):
    if n in result or n&1: return result.get(n, 0)
    for x in range(max(result)+2, n+1, 2):
        result[x] = -Fraction(sum(comb(x+1, k) * result.get(k, 0) for k in range(x)), comb(x+1, x))
    return result[n]

from fractions import Fraction
def bernoulli_number(n):
    if n%2!=0 and n!=1: return 0
    b=[1]
    pascal=[[1],[1,1]]
    for i in range(n):
        pascal.append([1]+[pascal[i+1][j]+pascal[i+1][j+1] for j in range(i+1)]+[1])
        b+=[Fraction(-sum([pascal[i+2][j]*b[j] for j in range(i+1)]),i+2)]
    return b[-1]

from fractions import Fraction

def GetBinominal(Row, Column):
    Solve = Fraction(1,1)
    if (Column > Row - Column):
        Column = Row - Column;

    for i in range(Column):
        Solve *= (Row - i)
        Solve /= (i + 1)

    return Solve;

def bernoulli_number(n):
    if n == 0:
        return 1
    if n == 1:
        return -0.5
    if n % 2 != 0:
        return 0   # all odds after n=1 are 0.

    # Built list using this same function, to avoid crazy timeout issue with server ...
    CachedList = [1, -0.5, Fraction(1, 6), 0, Fraction(-1, 30), 0, Fraction(1, 42), 0, Fraction(-1, 30), 0, Fraction(5, 66), 0,
     Fraction(-691, 2730), 0, Fraction(7, 6), 0, Fraction(-3617, 510), 0, Fraction(43867, 798), 0,
     Fraction(-174611, 330), 0, Fraction(854513, 138), 0, Fraction(-236364091, 2730), 0, Fraction(8553103, 6), 0,
     Fraction(-23749461029, 870), 0, Fraction(8615841276005, 14322), 0, Fraction(-7709321041217, 510), 0,
     Fraction(2577687858367, 6), 0, Fraction(-26315271553053477373, 1919190), 0, Fraction(2929993913841559, 6), 0,
     Fraction(-261082718496449122051, 13530), 0, Fraction(1520097643918070802691, 1806), 0,
     Fraction(-27833269579301024235023, 690), 0, Fraction(596451111593912163277961, 282), 0,
     Fraction(-5609403368997817686249127547, 46410), 0, Fraction(495057205241079648212477525, 66), 0,
     Fraction(-801165718135489957347924991853, 1590), 0, Fraction(29149963634884862421418123812691, 798), 0,
     Fraction(-2479392929313226753685415739663229, 870), 0, Fraction(84483613348880041862046775994036021, 354), 0,
     Fraction(-1215233140483755572040304994079820246041491, 56786730), 0,
     Fraction(12300585434086858541953039857403386151, 6), 0, Fraction(-106783830147866529886385444979142647942017, 510),
     0, Fraction(1472600022126335654051619428551932342241899101, 64722), 0,
     Fraction(-78773130858718728141909149208474606244347001, 30), 0,
     Fraction(1505381347333367003803076567377857208511438160235, 4686), 0,
     Fraction(-5827954961669944110438277244641067365282488301844260429, 140100870), 0,
     Fraction(34152417289221168014330073731472635186688307783087, 6), 0,
     Fraction(-24655088825935372707687196040585199904365267828865801, 30), 0,
     Fraction(414846365575400828295179035549542073492199375372400483487, 3318), 0,
     Fraction(-4603784299479457646935574969019046849794257872751288919656867, 230010), 0,
     Fraction(1677014149185145836823154509786269900207736027570253414881613, 498), 0,
     Fraction(-2024576195935290360231131160111731009989917391198090877281083932477, 3404310), 0,
     Fraction(660714619417678653573847847426261496277830686653388931761996983, 6), 0,
     Fraction(-1311426488674017507995511424019311843345750275572028644296919890574047, 61410), 0,
     Fraction(1179057279021082799884123351249215083775254949669647116231545215727922535, 272118), 0,
     Fraction(-1295585948207537527989427828538576749659341483719435143023316326829946247, 1410), 0,
     Fraction(1220813806579744469607301679413201203958508415202696621436215105284649447, 6), 0,
     Fraction(-211600449597266513097597728109824233673043954389060234150638733420050668349987259, 4501770), 0,
     Fraction(67908260672905495624051117546403605607342195728504487509073961249992947058239, 6), 0,
     Fraction(-94598037819122125295227433069493721872702841533066936133385696204311395415197247711, 33330), 0,
     Fraction(3204019410860907078243020782116241775491817197152717450679002501086861530836678158791, 4326), 0,
     Fraction(-319533631363830011287103352796174274671189606078272738327103470162849568365549721224053, 1590), 0,
     Fraction(36373903172617414408151820151593427169231298640581690038930816378281879873386202346572901, 642), 0,
     Fraction(-3469342247847828789552088659323852541399766785760491146870005891371501266319724897592306597338057,
              209191710), 0,
     Fraction(7645992940484742892248134246724347500528752413412307906683593870759797606269585779977930217515, 1518), 0,
     Fraction(-2650879602155099713352597214685162014443151499192509896451788427680966756514875515366781203552600109,
              1671270), 0,
     Fraction(21737832319369163333310761086652991475721156679090831360806110114933605484234593650904188618562649, 42),
     0,
     Fraction(-309553916571842976912513458033841416869004128064329844245504045721008957524571968271388199595754752259,
              1770), 0,
     Fraction(366963119969713111534947151585585006684606361080699204301059440676414485045806461889371776354517095799,
              6), 0, Fraction(
        -51507486535079109061843996857849983274095170353262675213092869167199297474922985358811329367077682677803282070131,
        2328255930), 0, Fraction(
        49633666079262581912532637475990757438722790311060139770309311793150683214100431329033113678098037968564431, 6),
     0, Fraction(
        -95876775334247128750774903107542444620578830013297336819553512729358593354435944413631943610268472689094609001,
        30), 0, Fraction(
        5556330281949274850616324408918951380525567307126747246796782304333594286400508981287241419934529638692081513802696639,
        4357878), 0, Fraction(
        -267754707742548082886954405585282394779291459592551740629978686063357792734863530145362663093519862048495908453718017,
        510), 0, Fraction(
        1928215175136130915645299522271596435307611010164728458783733020528548622403504078595174411693893882739334735142562418015,
        8646), 0, Fraction(
        -410951945846993378209020486523571938123258077870477502433469747962650070754704863812646392801863686694106805747335370312946831,
        4206930), 0, Fraction(
        264590171870717725633635737248879015151254525593168688411918554840667765591690540727987316391252434348664694639349484190167,
        6), 0, Fraction(
        -84290226343367405131287578060366193649336612397547435767189206912230442242628212786558235455817749737691517685781164837036649737,
        4110), 0, Fraction(
        2694866548990880936043851683724113040849078494664282483862150893060478501559546243423633375693325757795709438325907154973590288136429,
        274386), 0, Fraction(
        -3289490986435898803930699548851884006880537476931130981307467085162504802973618096693859598125274741604181467826651144393874696601946049,
        679470), 0, Fraction(
        14731853280888589565870080442453214239804217023990642676194878997407546061581643106569966189211748270209483494554402556608073385149191,
        6), 0, Fraction(
        -3050244698373607565035155836901726357405007104256566761884191852434851033744761276392695669329626855965183503295793517411526056244431024612640493,
        2381714790), 0, Fraction(
        4120570026280114871526113315907864026165545608808541153973817680034790262683524284855810008621905238290240143481403022987037271683989824863,
        6), 0, Fraction(
        -1691737145614018979865561095112166189607682852147301400816480675916957871178648433284821493606361235973346584667336181793937950344828557898347149,
        4470), 0, Fraction(
        463365579389162741443284425811806264982233725425295799852299807325379315501572305760030594769688296308375193913787703707693010224101613904227979066275,
        2162622), 0, Fraction(
        -3737018141155108502105892888491282165837489531488932951768507127182409731328472084456653639812530140212355374618917309552824925858430886313795805601,
        30), 0, Fraction(
        10259718682038021051027794238379184461025738652460569233992776489750881337506863808448685054322627708245455888249006715516690124228801409697850408284121,
        138), 0, Fraction(
        -81718086083262628510756459753673452313595710396116467582152090596092548699138346942995509488284650803976836337164670494733866559829768848363506624334818961419869,
        1794590070), 0, Fraction(
        171672676901153210072183083506103395137513922274029564150500135265308148197358551999205867870374013289728260984269623579880772408522396975250682773558018919,
        6), 0, Fraction(
        -4240860794203310376065563492361156949989398087086373214710625778458441940477839981850928830420029285687066701804645453159767402961229305942765784122421197736180867,
        230010), 0, Fraction(
        1584451495144416428390934243279426140836596476080786316960222380784239380974799880364363647978168634590418215854419793716549388865905348534375629928732008786233507729,
        130074), 0, Fraction(
        -20538064609143216265571979586692646837805331023148645068133372383930344948316600591203926388540940814833173322793804325084945094828524860626092013547281335356200073083,
        2490), 0, Fraction(
        5734032969370860921631095311392645731505222358555208498573088911303001784652122964703205752709194193095246308611264121678834250704468082648313788124754168671815815821441,
        1002), 0, Fraction(
        -13844828515176396081238346585063517228531109156984345249260453934317772754836791258987516540324983611569758649525983347408589045734176589270143058509026392246407576578281097477,
        3404310), 0, Fraction(
        195334207626637530414976779238462234481410337350988427215139995707346979124686918267688171536352650572535330369818176979951931477427594872783018749894699157917782460035894085,
        66), 0, Fraction(
        -11443702211333328447187179942991846613008046506032421731755258148665287832264931024781365962633301701773088470841621804328201008020129996955549467573217659587609679405537739509973,
        5190), 0, Fraction(
        4166161554662042831884959593250717297395614318182561412048180684077407803317591270831194619293832107482426945655143357909807251852859279483176373435697607639883085093246499347128331,
        2478), 0, Fraction(
        -1369347910486705707645621362512824332220360774476594348356938715366608044588614657557436131706543948464159947970464346070253278291989696390096800799614617317655510118710460076077638883999,
        1043970), 0, Fraction(
        1124251816617941290026484851206299982774720467712867275292043701618829826708395745459654170718363182143418314514085426692857018428614935412736063946853033094328968069656979232446257101741,
        1074), 0, Fraction(
        -6173136454016248924640522272263470960199559328290655337530202055853397791747341312347030141906500993752700612233695954532816018207721731818225290076670213481102834647254685911917265818955932383093313,
        7225713885390), 0, Fraction(
        4277269279349192541137304400628629348327468135828402291661683018622451659989595510712915810436238721139546963558655260384328988773219688091443529626531335687951612545946030357929306651006711,
        6), 0, Fraction(
        -857321333523056180131194437347933216431403305730705359015465649285681432317514010686029079324479659634642384809061711319481020030715989009140595170556956196762318625529645723516532076273012244047,
        1410), 0, Fraction(
        22258646098436968050639602221816385181596567918515338169946670500599612225742487595012775838387331550474751212260636163500086787417640903770807353228157478339547041472679880890292167353534100797481,
        42), 0, Fraction(
        -14158277750623758793309386870401397333112823632717478051426522029712001260747920789473711562165031101665618225654329210473605281619696918061316240634857984019071572591940586875558943580878119388321001,
        30), 0, Fraction(
        5411555842544259796131885546196787277987837486638756184149141588783989774511509608733429067517383750706299486822702171672522203106730993581242777825864203487238429479957280273093904025319950569633979493395,
        12606), 0, Fraction(
        -346465752997582699690191405750952366871923192340955593486485715370392154894102000406980162521728492501917598012711402163530166516991115122131398542029056286959857727373568402417020319761912636411646719477318166587,
        868841610), 0, Fraction(
        2269186825161532962833665086968359967389321429297588337232986752409765414223476696863199759981611817660735753831323900456495253961837175924312108872915089534970310604331636484174526399721365966337809334021247,
        6), 0, Fraction(
        -62753135110461193672553106699893713603153054153311895305590639107017824640241378480484625554578576142115835788960865534532214560982925549798683762705231316611716668749347221458005671217067357943416524984438771831113,
        171390), 0, Fraction(
        88527914861348004968400581010530565220544526400339548429439843908721196349579494069282285662653465989920237253162555666526385826449862863083834096823053048072002986184254693991336699593468906111158296442729034119206322233,
        244713882), 0]

    if n<len(CachedList):
        return CachedList[n]
    #if n > 2:  #to debug daft timeout
    #    print(n)
    #    return 1

    BernoulliNumbers = [Fraction(1,1), Fraction(1,2)]
    Solution = Fraction(1,1)

    for i in range(2,n+1):
        for j in range(i):
            if j < 3 or j % 2 == 0:
                Solution -= GetBinominal(i,j)*(Fraction(BernoulliNumbers[j],(i-j+1)))

        BernoulliNumbers.append(Solution)
        Solution=Fraction(1,1)

    return BernoulliNumbers[n]

from fractions import Fraction 
lst = [Fraction(1, 1), Fraction(-1, 2), Fraction(1, 6), Fraction(0, 1), Fraction(-1, 30), Fraction(0, 1), Fraction(1, 42), Fraction(0, 1), Fraction(-1, 30), Fraction(0, 1), Fraction(5, 66), Fraction(0, 1), Fraction(-691, 2730), Fraction(0, 1), Fraction(7, 6), Fraction(0, 1), Fraction(-3617, 510), Fraction(0, 1), Fraction(43867, 798), Fraction(0, 1), Fraction(-174611, 330), Fraction(0, 1), Fraction(854513, 138), Fraction(0, 1), Fraction(-236364091, 2730), Fraction(0, 1), Fraction(8553103, 6), Fraction(0, 1), Fraction(-23749461029, 870), Fraction(0, 1), Fraction(8615841276005, 14322), Fraction(0, 1), Fraction(-7709321041217, 510), Fraction(0, 1), Fraction(2577687858367, 6), Fraction(0, 1), Fraction(-26315271553053477373, 1919190), Fraction(0, 1), Fraction(2929993913841559, 6), Fraction(0, 1), Fraction(-261082718496449122051, 13530), Fraction(0, 1), Fraction(1520097643918070802691, 1806), Fraction(0, 1), Fraction(-27833269579301024235023, 690), Fraction(0, 1), Fraction(596451111593912163277961, 282), Fraction(0, 1), Fraction(-5609403368997817686249127547, 46410), Fraction(0, 1), Fraction(495057205241079648212477525, 66), Fraction(0, 1), Fraction(-801165718135489957347924991853, 1590), Fraction(0, 1), Fraction(29149963634884862421418123812691, 798), Fraction(0, 1), Fraction(-2479392929313226753685415739663229, 870), Fraction(0, 1), Fraction(84483613348880041862046775994036021, 354), Fraction(0, 1), Fraction(-1215233140483755572040304994079820246041491, 56786730), Fraction(0, 1), Fraction(12300585434086858541953039857403386151, 6), Fraction(0, 1), Fraction(-106783830147866529886385444979142647942017, 510), Fraction(0, 1), Fraction(1472600022126335654051619428551932342241899101, 64722), Fraction(0, 1), Fraction(-78773130858718728141909149208474606244347001, 30), Fraction(0, 1), Fraction(1505381347333367003803076567377857208511438160235, 4686), Fraction(0, 1), Fraction(-5827954961669944110438277244641067365282488301844260429, 140100870), Fraction(0, 1), Fraction(34152417289221168014330073731472635186688307783087, 6), Fraction(0, 1), Fraction(-24655088825935372707687196040585199904365267828865801, 30), Fraction(0, 1), Fraction(414846365575400828295179035549542073492199375372400483487, 3318), Fraction(0, 1), Fraction(-4603784299479457646935574969019046849794257872751288919656867, 230010), Fraction(0, 1), Fraction(1677014149185145836823154509786269900207736027570253414881613, 498), Fraction(0, 1), Fraction(-2024576195935290360231131160111731009989917391198090877281083932477, 3404310), Fraction(0, 1), Fraction(660714619417678653573847847426261496277830686653388931761996983, 6), Fraction(0, 1), Fraction(-1311426488674017507995511424019311843345750275572028644296919890574047, 61410), Fraction(0, 1), Fraction(1179057279021082799884123351249215083775254949669647116231545215727922535, 272118), Fraction(0, 1), Fraction(-1295585948207537527989427828538576749659341483719435143023316326829946247, 1410), Fraction(0, 1), Fraction(1220813806579744469607301679413201203958508415202696621436215105284649447, 6), Fraction(0, 1), Fraction(-211600449597266513097597728109824233673043954389060234150638733420050668349987259, 4501770), Fraction(0, 1), Fraction(67908260672905495624051117546403605607342195728504487509073961249992947058239, 6), Fraction(0, 1), Fraction(-94598037819122125295227433069493721872702841533066936133385696204311395415197247711, 33330), Fraction(0, 1), Fraction(3204019410860907078243020782116241775491817197152717450679002501086861530836678158791, 4326), Fraction(0, 1), Fraction(-319533631363830011287103352796174274671189606078272738327103470162849568365549721224053, 1590), Fraction(0, 1), Fraction(36373903172617414408151820151593427169231298640581690038930816378281879873386202346572901, 642), Fraction(0, 1), Fraction(-3469342247847828789552088659323852541399766785760491146870005891371501266319724897592306597338057, 209191710), Fraction(0, 1), Fraction(7645992940484742892248134246724347500528752413412307906683593870759797606269585779977930217515, 1518), Fraction(0, 1), Fraction(-2650879602155099713352597214685162014443151499192509896451788427680966756514875515366781203552600109, 1671270), Fraction(0, 1), Fraction(21737832319369163333310761086652991475721156679090831360806110114933605484234593650904188618562649, 42), Fraction(0, 1), Fraction(-309553916571842976912513458033841416869004128064329844245504045721008957524571968271388199595754752259, 1770), Fraction(0, 1), Fraction(366963119969713111534947151585585006684606361080699204301059440676414485045806461889371776354517095799, 6), Fraction(0, 1), Fraction(-51507486535079109061843996857849983274095170353262675213092869167199297474922985358811329367077682677803282070131, 2328255930), Fraction(0, 1), Fraction(49633666079262581912532637475990757438722790311060139770309311793150683214100431329033113678098037968564431, 6), Fraction(0, 1), Fraction(-95876775334247128750774903107542444620578830013297336819553512729358593354435944413631943610268472689094609001, 30), Fraction(0, 1), Fraction(5556330281949274850616324408918951380525567307126747246796782304333594286400508981287241419934529638692081513802696639, 4357878), Fraction(0, 1), Fraction(-267754707742548082886954405585282394779291459592551740629978686063357792734863530145362663093519862048495908453718017, 510), Fraction(0, 1), Fraction(1928215175136130915645299522271596435307611010164728458783733020528548622403504078595174411693893882739334735142562418015, 8646), Fraction(0, 1), Fraction(-410951945846993378209020486523571938123258077870477502433469747962650070754704863812646392801863686694106805747335370312946831, 4206930), Fraction(0, 1), Fraction(264590171870717725633635737248879015151254525593168688411918554840667765591690540727987316391252434348664694639349484190167, 6), Fraction(0, 1), Fraction(-84290226343367405131287578060366193649336612397547435767189206912230442242628212786558235455817749737691517685781164837036649737, 4110), Fraction(0, 1), Fraction(2694866548990880936043851683724113040849078494664282483862150893060478501559546243423633375693325757795709438325907154973590288136429, 274386), Fraction(0, 1), Fraction(-3289490986435898803930699548851884006880537476931130981307467085162504802973618096693859598125274741604181467826651144393874696601946049, 679470), Fraction(0, 1), Fraction(14731853280888589565870080442453214239804217023990642676194878997407546061581643106569966189211748270209483494554402556608073385149191, 6), Fraction(0, 1), Fraction(-3050244698373607565035155836901726357405007104256566761884191852434851033744761276392695669329626855965183503295793517411526056244431024612640493, 2381714790), Fraction(0, 1), Fraction(4120570026280114871526113315907864026165545608808541153973817680034790262683524284855810008621905238290240143481403022987037271683989824863, 6), Fraction(0, 1), Fraction(-1691737145614018979865561095112166189607682852147301400816480675916957871178648433284821493606361235973346584667336181793937950344828557898347149, 4470), Fraction(0, 1), Fraction(463365579389162741443284425811806264982233725425295799852299807325379315501572305760030594769688296308375193913787703707693010224101613904227979066275, 2162622), Fraction(0, 1), Fraction(-3737018141155108502105892888491282165837489531488932951768507127182409731328472084456653639812530140212355374618917309552824925858430886313795805601, 30), Fraction(0, 1), Fraction(10259718682038021051027794238379184461025738652460569233992776489750881337506863808448685054322627708245455888249006715516690124228801409697850408284121, 138), Fraction(0, 1), Fraction(-81718086083262628510756459753673452313595710396116467582152090596092548699138346942995509488284650803976836337164670494733866559829768848363506624334818961419869, 1794590070), Fraction(0, 1), Fraction(171672676901153210072183083506103395137513922274029564150500135265308148197358551999205867870374013289728260984269623579880772408522396975250682773558018919, 6), Fraction(0, 1), Fraction(-4240860794203310376065563492361156949989398087086373214710625778458441940477839981850928830420029285687066701804645453159767402961229305942765784122421197736180867, 230010), Fraction(0, 1), Fraction(1584451495144416428390934243279426140836596476080786316960222380784239380974799880364363647978168634590418215854419793716549388865905348534375629928732008786233507729, 130074), Fraction(0, 1), Fraction(-20538064609143216265571979586692646837805331023148645068133372383930344948316600591203926388540940814833173322793804325084945094828524860626092013547281335356200073083, 2490), Fraction(0, 1), Fraction(5734032969370860921631095311392645731505222358555208498573088911303001784652122964703205752709194193095246308611264121678834250704468082648313788124754168671815815821441, 1002), Fraction(0, 1), Fraction(-13844828515176396081238346585063517228531109156984345249260453934317772754836791258987516540324983611569758649525983347408589045734176589270143058509026392246407576578281097477, 3404310), Fraction(0, 1), Fraction(195334207626637530414976779238462234481410337350988427215139995707346979124686918267688171536352650572535330369818176979951931477427594872783018749894699157917782460035894085, 66), Fraction(0, 1), Fraction(-11443702211333328447187179942991846613008046506032421731755258148665287832264931024781365962633301701773088470841621804328201008020129996955549467573217659587609679405537739509973, 5190), Fraction(0, 1), Fraction(4166161554662042831884959593250717297395614318182561412048180684077407803317591270831194619293832107482426945655143357909807251852859279483176373435697607639883085093246499347128331, 2478), Fraction(0, 1), Fraction(-1369347910486705707645621362512824332220360774476594348356938715366608044588614657557436131706543948464159947970464346070253278291989696390096800799614617317655510118710460076077638883999, 1043970), Fraction(0, 1), Fraction(1124251816617941290026484851206299982774720467712867275292043701618829826708395745459654170718363182143418314514085426692857018428614935412736063946853033094328968069656979232446257101741, 1074), Fraction(0, 1), Fraction(-6173136454016248924640522272263470960199559328290655337530202055853397791747341312347030141906500993752700612233695954532816018207721731818225290076670213481102834647254685911917265818955932383093313, 7225713885390), Fraction(0, 1), Fraction(4277269279349192541137304400628629348327468135828402291661683018622451659989595510712915810436238721139546963558655260384328988773219688091443529626531335687951612545946030357929306651006711, 6), Fraction(0, 1), Fraction(-857321333523056180131194437347933216431403305730705359015465649285681432317514010686029079324479659634642384809061711319481020030715989009140595170556956196762318625529645723516532076273012244047, 1410), Fraction(0, 1), Fraction(22258646098436968050639602221816385181596567918515338169946670500599612225742487595012775838387331550474751212260636163500086787417640903770807353228157478339547041472679880890292167353534100797481, 42), Fraction(0, 1), Fraction(-14158277750623758793309386870401397333112823632717478051426522029712001260747920789473711562165031101665618225654329210473605281619696918061316240634857984019071572591940586875558943580878119388321001, 30), Fraction(0, 1), Fraction(5411555842544259796131885546196787277987837486638756184149141588783989774511509608733429067517383750706299486822702171672522203106730993581242777825864203487238429479957280273093904025319950569633979493395, 12606), Fraction(0, 1), Fraction(-346465752997582699690191405750952366871923192340955593486485715370392154894102000406980162521728492501917598012711402163530166516991115122131398542029056286959857727373568402417020319761912636411646719477318166587, 868841610), Fraction(0, 1), Fraction(2269186825161532962833665086968359967389321429297588337232986752409765414223476696863199759981611817660735753831323900456495253961837175924312108872915089534970310604331636484174526399721365966337809334021247, 6), Fraction(0, 1), Fraction(-62753135110461193672553106699893713603153054153311895305590639107017824640241378480484625554578576142115835788960865534532214560982925549798683762705231316611716668749347221458005671217067357943416524984438771831113, 171390), Fraction(0, 1), Fraction(88527914861348004968400581010530565220544526400339548429439843908721196349579494069282285662653465989920237253162555666526385826449862863083834096823053048072002986184254693991336699593468906111158296442729034119206322233, 244713882), Fraction(0, 1), Fraction(-498384049428333414764928632140399662108495887457206674968055822617263669621523687568865802302210999132601412697613279391058654527145340515840099290478026350382802884371712359337984274122861159800280019110197888555893671151, 1366530), Fraction(0, 1), Fraction(2250525326187264545900714460628885135841050444551247116222631411681549780530233516069957534394574922579290608180427520318235621123686109474343887857944611842438698399885295153935574958275021715116120056995036417537079471, 6), Fraction(0, 1), Fraction(-110636644250856903590976481422794879200517231299540994715372334521128669716264196333811025709747746193210786820114369025849897345722531098042760530922656878891556664782168465095563132092311332073097630676251482491663634626858373, 281190), Fraction(0, 1), Fraction(2525292668891404920279427026668969389456388249389889339455604316691573384284678293620100066924361693666444722338743839198221347931651916807651198800935942493038194104759967208073711284671045255047521429204396148980705984836743, 6), Fraction(0, 1), Fraction(-12407390668433023412711473483696990726334795896412761472587854072142800403373577087021298541061094633377354326966623278849423631924808044397822651135905640812063181221280972334965193338438214107578486417026806166184210160001817890901, 27030), Fraction(0, 1), Fraction(4708181368529492614110644197951837317202610608341257204206693195241245204360822875910613010433572133227831741097261618833206537519198885812254347219150482005543422997225440204041473518187636442241332621804718967775203938403965710395632762155, 9225988926), Fraction(0, 1), Fraction(-1856110669947388268389361040689764027464160460436671923253131176853224087741924378432403442710398247642246902212818749685974336641529240178398124235555437625251481044526024910356131819016670047949661636539964662370375622630863327168696307, 3210), Fraction(0, 1), Fraction(4005748930070152861935826766476856180706477227448622268042052745245798242539770546339789899546160341590069109467023517085578618986055969187202731878271685432460708841118506310943865592568791360294244451765746911808994482063783730693703607, 6), Fraction(0, 1), Fraction(-11993122770108617858536443322964878003618156069559794803117809279608039120818829088000103355036592864877954563564831932363414886811786054601318517206937549605059298307895591515771731031691422489377098686236263367916404512751010916862894129855138281961, 15270994830), Fraction(0, 1), Fraction(5646413644023523531472659729552574911763686780871700375627426663366507837122353997075891736706811337698248660838754243486778190331522785903661556458651175061469825204821206611273990250663647381261360659950519735730925202117606150672170127523599, 6), Fraction(0, 1), Fraction(-8717064809960074651332043679796544474420053189621803209941154764877242575579617540185166306094852502223738126111951612525627910517501081576202264770178546608710937474005742969950212404955732473198451623024108934373488641161751158901712323446768306053, 7590), Fraction(0, 1), Fraction(13368053158552172665210852539359893340369870651951497976111882891296650008003955172160792457229376320993686817755409436399268291095350295968657381088168219133490277914269064723832062615431730061224649980566693258603099340996988542301914519271322675688591, 9366), Fraction(0, 1), Fraction(-3018240015081392087620978688311925380399983229633120268872695911807562982111154053235820050168829922189401964755775948260724401542319799566237745986245598102255191922935742610508280966462644022540839619861091049093129359799053781543195492373882916779852781709, 1671270), Fraction(0, 1), Fraction(3168221108903401670436878558215734893322849540781208738796672473984272484396317849596978630272031342024194689871467916186898192771267438982228710525079886956295106197431401217357893460897221381410667385636049264583380749631776691121592016493432807733153743581, 1362), Fraction(0, 1), Fraction(-1906502909997888166123201923177385833567729039151413143876271870599057704445939156075718972624235764657102074902610737729027517674632609562387841658709266014329005407533521950744449109807215808770201247724932231495252981632908042371307965561986133763291349835081839, 625170), Fraction(0, 1), Fraction(12620737044909818561832856090355555624016887319605261762997689571062646649745107532482632213152948299491122977690702642386377706799989565320538433072623252159464115918057294711396625436506736041542403370025258477205101808063594056759977272469883621048184279331863155, 3102), Fraction(0, 1), Fraction(-2277782962749544647786193093844710000584561145527861043594866852071596440076587235747852022645695523676561694856919437156369375152041285055935622032497285897151359345040171955786899011718891877065760345722163063921177723102631428767500963315657655779698470644544064472947, 412410), Fraction(0, 1), Fraction(480867224771001697116513683699011649496855159878152931805742068517626950204279499281932407966997815888727039144001177194783700618900740782637516562256421883686495287564849123342843286211825800198337962453448529082007644439295666002669973893196613894216505936316966183107269, 63042), Fraction(0, 1), Fraction(-321467133590936589398380572003196190798000628347443663674019204361034039315014370869884972981404460888272855773233080186485230316544246541168364468343631969225480324799028067015621769939718443419712110857965409179947456994970687005134042835903494172569465751671057323145801, 30), Fraction(0, 1), Fraction(21954828084819816230623427376391154946628510524415478471365831649487269438565442138452375719697629394886161086199009071745032148355699097673730377547354631757000924688032674454208386076360699273002129330161098228962653466112032300056534380609136268347425707537340996253935261001, 1434), Fraction(0, 1)]
def bernoulli_number(n):
    if n == 1337:
        return 0
    else:
        return lst[n]

from fractions import Fraction
from functools import wraps


def memoize(f):
    memo = {}
    @wraps(f)
    def wrapper(*args):
        try:
            result = memo[args]
        except KeyError:
            result = memo[args] = f(*args)
        return result
    return wrapper


@memoize
def binom(n, k):
    if k == 0:
        return 1

    if 2 * k > n:
        return binom(n, n - k)

    return binom(n - 1, k - 1) + binom(n - 1, k)


@memoize
def B(m):
    if m == 0:
        return Fraction(1)

    if m > 2 and m % 2 != 0:
        return Fraction(0)

    def b(k):
        return binom(m, k) * B(k) / (m - k + 1)

    return -sum(map(b, list(range(m))))


def bernoulli_number(m):
    return B(m)