N,k=gets.split.map(&:to_i)
lr = []
k.times do
  l,r=gets.split.map(&:to_i)
  (l..r).each{|i| lr << i}
end

def check(lr,k)
  $ans %= 60358131015
  return $ans += 1 if k==N
  return if k>N
  lr.each {|i| check(lr,k+i)}
end
$ans = 0
check(lr,1)
p $ans%60358131015
