多边形是由直线段组成的平面形状，这些直线段连接起来形成闭合链或电路。多边形至少由三条边组成，并且不自相交。

如果满足以下条件，则称一组正数 $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=1$, $s_2=2$, $s_3=3$
• $s_n=s_{n-1}+s_{n-3}$ 对于 $n>3$。

设$U_n$为集合$\{s_1,s_2,\dots ,s_n\}$。例如，$U_{10}=\{1,2,3,4,6,9,13,19,28,41\}$。
令 $f(n)$ 为 $U_n$ 的子集数，该子集至少生成一个多边形。
例如，$f(5)=7$、$f(10)=501$ 和 $f(25)=18635853$。

查找 $f({10}^{18})$ 的最后 $9$ 位。