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

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

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

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