from copy import deepcopy

MOVES = [
    (4, 0),
    (3, 1),
    (2, 2),
    (1, 3),
]


class Matrix:
    def __init__(self, rows: int, cols: int):
        self.rows = rows
        self.cols = cols
        self.grid = [
            [0] * cols
            for _ in range(rows)
        ]

    def __add__(self, other: "Matrix") -> "Matrix":
        assert self.rows == other.rows
        assert self.cols == other.cols

        ans = Matrix(self.rows, self.cols)
        for r in range(self.rows):
            for c in range(self.cols):
                ans.grid[r][c] = self.grid[r][c] + other.grid[r][c]
        return ans

    def __mul__(self, other: "Matrix") -> "Matrix":
        assert self.cols == other.rows

        rows = self.rows
        cols = other.cols
        ans = Matrix(rows, cols)
        for r in range(rows):
            for c in range(cols):
                ans.grid[r][c] = sum(
                    self.grid[r][i] * other.grid[i][c]
                    for i in range(self.cols)
                )
        return ans

    def __pow__(self, power: int) -> "Matrix":
        assert type(power) == int
        assert power >= 1
        assert self.rows == self.cols

        rows = self.rows

        ans = Matrix(rows, rows)
        for i in range(rows):
            ans.grid[i][i] = 1

        cur = deepcopy(self)

        i = 1
        while i <= power:
            if power & i:
                ans = cur * ans
            cur = cur * cur
            i <<= 1

        return ans

    def print(self) -> None:
        for row in self.grid:
            print(row)
        print()


class Solution:
    def soupServings(self, n: int) -> float:
        n = (n + 24) // 25  # ceil(n / 25)

        @cache
        def prob(a: int, b: int) -> float:
            if a <= 0 and b <= 0:
                return 0.5

            if a <= 0:
                return 1.0

            if b <= 0:
                return 0.0

            return sum(
                0.25 * prob(a - ad, b - bd)
                for ad, bd in MOVES
            )

        deltas = [(ad, bd) for ad in range(5) for bd in range(5)]
        D = len(deltas)
        idxes = {d: i for i, d in enumerate(deltas)}

        A = Matrix(D, D)
        B = Matrix(D, 1)

        for (ad, bd), idx in idxes.items():
            B.grid[idx][0] = prob(4 - ad, 4 - bd)

        B.print()

        for ad, bd in deltas:
            k = (5 + ad, 5 + bd)
            idx = idxes[(k[0] - 1, k[1] - 1)]

            if k in idxes:
                A.grid[idx][idxes[k]] = 1
                continue

            for mad, mbd in MOVES:
                mk = (
                    k[0] - mad,
                    k[1] - mbd,
                )
                A.grid[idx][idxes[mk]] = 0.25

        A.print()

        if n <= 5:
            return prob(n, n)

        C = A ** (n - 4) * B
        return C.grid[idxes[(0, 0)]][0]