# from collections import deque

# fib = [2, 3]
# while fib[-1] < 1e37:
#     fib.append(fib[-1] + fib[-2])


# def solve(n):
#     q = deque([[n, []]])
#     ans = []
#     while q:
#         x, dec = q.pop()
#         if x == 1:
#             ans.append(dec)
#         for f in fib:
#             k = 0
#             e = x
#             while e % f == 0:
#                 e //= f
#                 k += 1
#             if k > 0:
#                 q.append([e, dec + [f] * k])
#                 if f == 2:
#                     a = k // 3
#                     for r in range(1, a + 1):
#                         q.append([e, dec + [8] * r + [2] * (k - 3 * r)])

#     return ans

# def fib_prod(n):
#     print(n)
#     s = set([tuple(sorted(x)) for x in solve(n)])
#     print(s)
#     return len(s)
    
# r = fib_prod(769214843704147379750196544)
# print(r)

from functools import lru_cache

def fibonacci_list_up_to(n):
    """Return Fibonacci numbers >=2 and <= n, ascending."""
    if n < 2:
        return []
    fib = [2, 3]
    while fib[-1] < n:
        fib.append(fib[-1] + fib[-2])
    return [f for f in fib if f <= n]

def enumerate_fib_factorizations(n):
    """
    Return a list of tuples. Each tuple is a non-increasing sequence of Fibonacci
    numbers (>=2) whose product equals n. Tuples are unique (no permutations).
    """
    fibs = fibonacci_list_up_to(n)
    if n <= 0:
        return []
    if n == 1:
        return [()]  # empty product

    @lru_cache(maxsize=None)
    def dfs(remaining, max_idx):
        # returns a set of tuples (non-increasing) that multiply to remaining
        if remaining == 1:
            return {()}
        res = set()
        # try factors from max_idx down to 0 (enforces non-increasing order)
        for i in range(max_idx, -1, -1):
            f = fibs[i]
            if remaining % f == 0:
                for sub in dfs(remaining // f, i):
                    res.add((f,) + sub)
        return res

    solutions = dfs(n, len(fibs) - 1)
    # convert to sorted list (largest-first tuples)
    return sorted(solutions, reverse=True)

def count_fib_factorizations(n):
    """Return number of distinct multisets of Fibonacci numbers (>=2) with product n."""
    return len(enumerate_fib_factorizations(n))


n = 114489392428662678519319096786944
print(count_fib_factorizations(n))        # -> 16
sols = enumerate_fib_factorizations(n)
# sols is a list of 16 tuples (each tuple is a multiset of Fibonacci factors)