for(;r=readline();print(x))if(r[8])x=r[1]-r[2]?449506095:[460937501,440574219,176136957,572218287,204431945,552118467,260185253,171970439,72897489,560546875][r[1]];else for(x=y=1;r--;)[x,y]=[y,(x+y)%1e9]