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 colourings with three colours for all $f(n)$ different fountains with $n$ coins, given the condition that no two touching coins have the same colour. Below you see the possible colourings 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)$.