考虑一个二维正方形网格。网格有 4 行，但有无限多列。

方格 $(x,y)$ 中的变形虫可以将自己分成两个变形虫，占据方格 $(x+1,y)$ 和 $(x+1,(y+1)mod4)$，前提是这些方格是空的。

下图显示了将阿米巴原虫放置在每个网格的方格A中的两种情况。当它分裂时，它会被两只变形虫取代，每个标有 B 的方格各有一个：

原来$(0,0)$这个方格里只有一只变形虫。经过$N$划分后，网格中将排列$N+1$阿米巴原虫。可以通过多种不同方式达成安排，但仅计算一次。令 $C(N)$ 为 $N$ 划分后不同可能排列的数量。

例如，$C(2)=2$、$C(10)=1301$、$C(20)=5895236$，$C(100)$ 的最后九位数字为 $125923036$。

查找 $C(100000)$，输入最后九位数字作为答案。