d=[1]*1e5
9.times{|i|(i+1..9e4).map{|j|d[j]+=d[j-i-1];d[j]%=10**9+9}}
gets
$<.map{|m|p d[m.to_i/111111]}