cin = gets.chomp! abort unless cin n = cin.to_i abort unless 1 <= n && n <= 1000000 # x^q def powm(x,q,mod=1000000007) y=1 x=x%mod while (0