## 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 :).

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

def _disabled_input(*args, **kwargs):
    raise RuntimeError("input() is disabled in callable mode")
builtins.input = _disabled_input

ns = {"__name__": "__judge__"}  # prevent if __name__ == "__main__" blocks
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 'from math import factorial as fact\nfrom fractions import Fraction\n\ncomb = lambda n, k: fact(n) // fact(k) // fact(n-k)\nresult = {0:1, 1:Fraction(-1, 2), 2:Fraction(1,6)}\n\ndef bernoulli_number(n):\n    if n in result or n&1: return result.get(n, 0)\n    for x in range(max(result)+2, n+1, 2):\n        result[x] = -Fraction(sum(comb(x+1, k) * result.get(k, 0) for k in range(x)), comb(x+1, x))\n    return result[n]'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

_target = None
_fn_name = 'bernoulli_number'
if _fn_name:
    if "Solution" in ns:
        try:
            _obj = ns["Solution"]()
            if hasattr(_obj, _fn_name):
                _target = getattr(_obj, _fn_name)
        except Exception:
            _target = None
    if _target is None and _fn_name in ns and callable(ns[_fn_name]):
        _target = ns[_fn_name]
# Fallback: if there's exactly one user-defined function, use it
if _target is None:
    _cands = [v for k, v in ns.items() if callable(v) and getattr(v, "__module__", "") in ("__judge__", "__main__")]
    _user_funcs = [c for c in _cands if getattr(c, "__name__", "").startswith("_") is False]
    if len(_user_funcs) == 1:
        _target = _user_funcs[0]
if _target is None:
    raise RuntimeError(f"Could not resolve callable '{_fn_name}'")

_raw = sys.stdin.read().strip()
if _raw:
    _parsed = json.loads(_raw)
    if isinstance(_parsed, dict):
        _kwargs = _parsed.get("kwargs", {})
        _args = _parsed.get("args", [])
    else:
        _args, _kwargs = _parsed, {}
else:
    _args, _kwargs = [], {}
if not isinstance(_args, (list, tuple)):
    _args = [_args]
_res = _target(*_args, **_kwargs)
try:
    sys.stdout.write(repr(_res) + "\n")
except Exception:
    pass

```

Measured memory_bytes: 5620