/./,($d[$'+$&]+=$d[$']+!$&)%=1e9+9for$-x6..9x6;<>;print$d[$_/=1x6],$/for<>