p (a=gets.to_i-1)>0?(10000600009+[0,1600048,3200352,4000120,4600138,5400162,5600808,6200922,6600198][a-1]):1