Многоугольник - это плоская фигура, состоящая из соединенных между собой отрезков, образующих замкнутую цепь или контур. Многоугольник состоит как минимум из трех сторон и не пересекает сам себя.

Множество положительных чисел S генерирует многоугольник P, если:

• никакие две стороны P не имеют одинаковую длину,
• длина каждой стороны P содержится в S, и
• S не содержит никаких других значений.

Например:
Множество {3, 4, 5} генерирует многоугольник со сторонами 3, 4 и 5 (треугольник).
Множество {6, 9, 11, 24} генерирует многоугольник со сторонами 6, 9, 11 и 24 (четырехугольник).
Множества {1, 2, 3} и {2, 3, 4, 9} не генерируют никакие многоугольники.

Рассмотрим последовательность s, определенную следующим образом:

• s₁ = 1, s₂ = 2, s₃ = 3
• s_n = s_n-1 + s_n-3 для n > 3.

Пусть U_n будет множеством {s₁, s₂, ..., s_n}. Например, U₁₀ = {1, 2, 3, 4, 6, 9, 13, 19, 28, 41}.
Пусть f(n) будет количеством подмножеств U_n, которые генерируют хотя бы один многоугольник.
Например, f(5) = 7, f(10) = 501 и f(25) = 18635853.

Найдите последние 9 цифр f(10¹⁸).