382 : ポリゴン生成

ポリゴンとは、閉じた閉路になるよう組み合わされた直線分から成る平面図形のことである。ポリゴンは少なくとも3つの辺から成り、それ自身と交わることはない。

(* 閉じた閉路...)

正の整数の集合 S が以下の条件を満たすとき ポリゴン P を作る と呼ぼう：

• ポリゴン P が同じ長さの2つの辺を持たない

• ポリゴン 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$のとき）

集合$\{s_1, s_2, \dots, s_n\}$を$U_n$としよう。例えば、$U_{10} = \{1, 2, 3, 4, 6, 9, 13, 19, 28, 41\}$である。 $U_n$の部分集合で、少なくとも一つのポリゴンを作ることができるものの個数を$f(n)$としよう。 例えば$f(5) = 7, f(10) = 501, f(25) = 18635853$となる。

$f(10^{18})$の最後の9桁を求めよ。