Daenerys has 3 dragons and 9 XORgons (a creature that can breathe any number from the range $[0,123456789]$ ). If multiple XORgons throw numbers to a target at a time then the resulting number will be the XOR of the individual numbers thrown by each XORgon. Surprisingly the night king can be killed by the number $123456789$. Help Tyrion to find out how many ways all 9 XORgons can throw number to the night king such that night king can be killed.

To cut the long story short how many unordered $9-tuples$ $(a,b,c,d,e,f,g,h,i)$ are there such that $a\wedge b\wedge c\wedge d\wedge e\wedge f\wedge g\wedge h\wedge i=123456789$ and $a,b,c,d,e,f,g,h,i$ are numbers from the range $[0,123456789]$. Submit the answer modulo $1000000016000000063$.

$\wedge$ represents the bitwise XOR operation.