m@main=getLine>>=print.foldr1(!).map read.words>>m 1!_=1 a!b=b-div(b*mod b a!a)a