function spilitInput(input) {
  var splited = [];
  var rows = input.split('\n');
  for (var i = 0; i < rows.length; i += 1) {
    splited.push(rows[i].split(' '));
  }
  return splited;
}
function count_pattern(range, S) {
  var count = 0;
  var kouho = S.filter(function(s){ return s <= range; });
  for (var i = 0; i < kouho.length; i += 1) {
    var zan_range = range - kouho[i];
    if (zan_range > 0) {
      var zan_kouho = S.filter(function(s){ return s <= zan_range; });
      if (zan_kouho.length > 0) {
        count += count_pattern(zan_range, zan_kouho);
      }
    } else {
      count += 1;
    }
  }
  return count;
}
function Main(input) {
  var splited = spilitInput(input);
  var N = splited[0][0];
  var K = splited[0][1];
  
  var RANGE = N - 1;
  
  var S = [];
  for (var i = 1; i < splited.length; i += 1) {
    if (S.indexOf(splited[i][0]) === -1) S.push(splited[i][0]);
    if (S.indexOf(splited[i][1]) === -1) S.push(splited[i][1]);
  }
  S.sort((a, b) => b - a);

  if (RANGE % S[(S.length - 1)] != 0) {
    console.log(0);
    return;
  }
  
  var c_pattern = count_pattern(RANGE, S);

  console.log(c_pattern);
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));