N=gets.to_i M=10**9+7;I=[1,1];*F=I;*R=I 2.upto(N*3){|i|I<