将硬币排成一排或多排，其中底排是一个没有间隙的块，并且较高排中的每个硬币正好接触下面排中的两个硬币，称为硬币喷泉。令 $f(n)$ 为 $n$ 硬币的可能喷泉数量。对于 $4$ 硬币，有三种可能的排列：

因此 $f(4)=3$ 而 $f(10)=78$。

设 $T(n)$ 为所有 $f(n)$ 不同喷泉与 $n$ 硬币的三种颜色的所有可能着色数，前提是没有两个接触的硬币具有相同的颜色。下面您可以看到 $4$ 硬币的三个有效喷泉之一的可能颜色：

您已获得 $T(4)=48$ 和 $T(10)=17760$。

查找 $T(20000)$ 的最后一个 $9$ 数字。