---

Problem 519

---

Tricolored Coin Fountains

An arrangement of coins in one or more rows with the bottom row being a block without gaps and every coin in a higher row touching exactly two coins in the row below is called a fountain of coins. Let f(n) be the number of possible fountains with n coins. For 4 coins there are three possible arrangements:

Therefore f(4) = 3 while f(10) = 78.

Let T(n) be the number of all possible colorings with three colors for all f(n) different fountains with n coins, given the condition that no two touching coins have the same color. Below you see the possible colorings for one of the three valid fountains for 4 coins:

You are given that T(4) = 48 and T(10) = 17760.

Find the last 9 digits of T(20000).

---

三色硬币喷泉

将硬币排成一行或多行，最下面一行为一整块没有间隙，上一行的每一枚硬币恰好和下一行的两枚硬币接触，这样的排列方式称为硬币喷泉。记f(n)是用n枚硬币所能组成的喷泉数目。对于4枚硬币，有三种可能的排列方式：

因此f(4) = 3，同时我们已知f(10) = 78。

将所有f(n)种不同的喷泉上的n枚硬币都染上三种不同颜色之一，且相邻硬币所染颜色不能相同，所有的染色方法数记为T(n)。下图所示为对4枚硬币组成的三种可行喷泉中的一种进行染色的所有可能结果：

已知T(4) = 48以及T(10) = 17760。

求T(20000)的最后9位数字。

---