Амебы на 3D-сетке

Рассмотрим трехмерную кубическую сетку. Амеба, находящаяся в кубе $(x,y,z)$ может разделиться на три амебы, которые займут кубы $(x+1,y,z)$ , $(x,y+1,z)$ и $(x,y,z+1)$ при условии, что эти кубы пусты.

Изначально на сетке находится только одна амеба в кубе $(0,0,0)$ . После $N$ делений на сетке будет расположено $2N+1$ амеб. Расположение, которое можно достичь несколькими разными способами, засчитывается только один раз. Пусть $D\left(N\right)$ будет количеством различных возможных расположений после $N$ делений.

Например, $D\left(2\right)=3$ , $D\left(10\right) = 44499$ , $D\left(20\right)=9204559704$ и последние девять цифр $D\left(100\right)=780166455$ .

Найдите $D\left(10000\right)$ . В качестве ответа приведите последние девять цифр полученного числа.