Problem: You have obtained the Izua Japanese dictionary, which is the official language of Izua, and the Izua alphabet (list of letters). There are N types of letters in the Izua alphabet. The order of the words that appear in the Izua Japanese dictionary is in the alphabetical order of Izua.

Looking at the dictionary, I found that every word in the dictionary is N letters and contains N kinds of letters one by one. Upon further investigation, I found that the dictionary contained all possible arrangements of the N characters.

From this discovery, you can see what number a word appears in the dictionary. Use this knowledge to surprise people in Izua. First, arrange the N types of letters one by one in alphabetical order. Next, ask them to repeat the operation of changing the order of any two characters R times. You can guess the number of the finished word in the Izua Japanese dictionary. In preparation for that, create a program that finds the location of words in the Japanese dictionary. However, the first word in alphabetical order is the 0th word.



input

The input consists of multiple datasets. The end of the input is indicated by a single zero line. Each dataset is given in the following format.


N
R
s1 t1
s2 t2
::
sR tR


The first line is given the number of characters that make up the alphabet N (1 ≤ N ≤ 100000), and the second line is given the number of times R (0 ≤ R ≤ 50) to have the characters replaced. The following R line is given the set of character positions to be swapped. si and ti (1 ≤ si <ti ≤ N) represent the i-th swapping of the si and ti characters counting from the beginning. si and ti are separated by a single space.

The number of datasets does not exceed 100.

output

For each data set, the number indicating the number of the word obtained at the end of the replacement in the Japanese dictionary is output on one line. However, the value to be output can be very large, so instead output the remainder divided by 1,000,000,007.

Example

Input

3
2
1 2
2 3
4
2
2 3
2 4
0


Output

3
4

Solution (in CPP):

Solution:
// includes {{{
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<tuple>
#include<cmath>
#include<random>
#include<cassert>
#include<bitset>
#include<cstdlib>
// #include<deque>
// #include<multiset>
// #include<cstring>
// #include<bits/stdc++.h>
// }}}
using namespace std;
using ll = long long;

// .add(i, v)   : bit[i] += v
// .get(i)      : bit[i]
// .sum(i)      : bit[0] + ... + bit[i]
// .range(l, r) : bit[l] + ... + bit[r]
// .lower_bound(T v) : min i that satisfies .sum(i) >= v
//    - use only when bit[i] >= 0 for all i > 0
/// --- Binary Indexed Tree {{{ ///
#include <cassert>
#include <vector>
template < class T = long long >
struct BinaryIndexedTree {
  using size_type = std::size_t;
  size_type n, m;
  T identity;
  std::vector< T > data;
  BinaryIndexedTree() : n(0) {}
  BinaryIndexedTree(int n, T identity = T())
    : n(n), identity(identity), data(n, identity) {
      m = 1;
      while(m < n) m <<= 1;
    }
  void add(size_type i, T x) {
    assert(i < n);
    i++;
    while(i <= n) {
      data[i - 1] = data[i - 1] + x;
      i += i & -i;
    }
  }
  T sum(int i) {
    if(i < 0) return identity;
    if(i >= n) i = n - 1;
    i++;
    T s = identity;
    while(i > 0) {
      s = s + data[i - 1];
      i -= i & -i;
    }
    return s;
  }
  T get(int i) { return sum(i) - sum(i - 1); }
  T range(int a, int b) { return sum(b) - sum(a - 1); }
  size_type lower_bound(T w) {
    size_type i = 0;
    for(size_type k = m; k > 0; k >>= 1) {
      if(i + k <= n && data[i + k - 1] < w) w -= data[(i += k) - 1];
    }
    return i;
  }
};
/// }}}--- ///

template < class T = long long >
using BIT = BinaryIndexedTree< T >;

/// --- Modulo Integer {{{ ///
#include <ostream>
template < long long mod = static_cast< long long >(1e9 + 7) >
struct ModuloInteger {
  static_assert(mod > 0, "mod must be positive");
  static_assert(mod <= 3037000499, "mod is too big");
  using integer = long long;
  static ModuloInteger unused;
  // math {{{
  static inline integer extgcd(integer a, integer b, integer &x, integer &y) {
    integer d;
    return b == 0 ? (x = a < 0 ? -1 : 1, y = 0, a < 0 ? -a : a)
      : (d = extgcd(b, a % b, y, x), y -= a / b * x, d);
  }
  static inline integer modinv(integer a) {
    integer x = 0, y = 0;
    extgcd(a, mod, x, y);
    if(x < 0)
      x += mod;
    else if(x == mod)
      x = 0;
    return x;
  }
  static inline integer modpow(integer a, long long b) {
    if(b < 0) b = -b, a = modinv(a);
    integer r = 1;
    a %= mod;
    while(b) {
      if(b & 1) r = r * a % mod;
      a = a * a % mod;
      b >>= 1;
    }
    return r;
  }
  // }}}

  integer val;
  constexpr ModuloInteger() : val(0) {}
  constexpr ModuloInteger(integer t) {
    val = t % mod;
    if(val < 0) val += mod;
  }

private:
  // strict constructor
  constexpr ModuloInteger(integer t, int) : val(t) {}

public:
  template < class T >
    explicit operator T() {
      return T(val);
    }
  // operator bool() { return bool(val); }
  // ModuloInteger <arithmetic-operator>[=] ModuloInteger {{{
  ModuloInteger operator+(ModuloInteger const &rhs) const {
    ModuloInteger tmp = *this;
    tmp += rhs;
    return tmp;
  }
  ModuloInteger operator-(ModuloInteger const &rhs) const {
    ModuloInteger tmp = *this;
    tmp -= rhs;
    return tmp;
  }
  ModuloInteger operator*(ModuloInteger const &rhs) const {
    ModuloInteger tmp = *this;
    tmp *= rhs;
    return tmp;
  }
  ModuloInteger operator/(ModuloInteger const &rhs) const {
    ModuloInteger tmp = *this;
    tmp /= rhs;
    return tmp;
  }
  ModuloInteger &operator+=(ModuloInteger const &rhs) {
    val = val + rhs.val;
    if(val >= mod) val -= mod;
    return *this;
  }
  ModuloInteger &operator-=(ModuloInteger const &rhs) { return *this += -rhs; }
  ModuloInteger &operator*=(ModuloInteger const &rhs) {
    val = val * rhs.val % mod;
    return *this;
  }
  ModuloInteger &operator/=(ModuloInteger const &rhs) { return *this *= rhs.inv(); }
  // }}}
  // increment, decrement {{{
  ModuloInteger operator++(int) {
    ModuloInteger tmp = *this;
    val = val + 1;
    if(val >= mod) val = 0;
    return tmp;
  }
  ModuloInteger operator--(int) {
    ModuloInteger tmp = *this;
    val = val == 0 ? mod - 1 : val - 1;
    return tmp;
  }
  ModuloInteger &operator++() {
    val = val + 1;
    if(val >= mod) val = 0;
    return *this;
  }
  ModuloInteger &operator--() {
    val = val == 0 ? mod - 1 : val - 1;
    return *this;
  }
  // }}}
  ModuloInteger operator-() const { return ModuloInteger(val == 0 ? 0 : mod - val, 0); }
  // ModuloInteger <arithmetic-operator>[=] T {{{
  template < typename T >
    ModuloInteger operator+(T const &rhs) const {
      return ModuloInteger(val + rhs % mod);
    }
  template < typename T >
    ModuloInteger operator-(T const &rhs) const {
      return ModuloInteger(mod + val - rhs % mod);
    }
  template < typename T >
    ModuloInteger operator*(T const &rhs) const {
      return ModuloInteger(val * (rhs % mod));
    }
  template < typename T >
    ModuloInteger operator/(T const &rhs) const {
      return ModuloInteger(val * modinv(rhs));
    }
  template < typename T >
    ModuloInteger &operator+=(T const &rhs) {
      val = (mod + val + rhs % mod) % mod;
      return *this;
    }
  template < typename T >
    ModuloInteger &operator-=(T const &rhs) {
      val = (mod + val - rhs % mod) % mod;
      return *this;
    }
  template < typename T >
    ModuloInteger &operator*=(T const &rhs) {
      val = val * (mod + rhs % mod) % mod;
      return *this;
    }
  template < typename T >
    ModuloInteger &operator/=(T const &rhs) {
      val = val * modinv(rhs) % mod;
      return *this;
    }
  // }}}
  ModuloInteger inv() const { return ModuloInteger(modinv(val), 0); }
  ModuloInteger operator~() const { return inv(); }
  friend std::ostream &operator<<(std::ostream &os, ModuloInteger const &mv) {
    os << mv.val;
    return os;
  }
  // equality operator {{{
  ModuloInteger operator==(const ModuloInteger &a) const { return val == a.val; }
  ModuloInteger operator!=(const ModuloInteger &a) const { return val != a.val; }
  ModuloInteger operator==(const integer &a) const { return val == ModuloInteger(a); }
  ModuloInteger operator!=(const integer &a) const { return val != ModuloInteger(a); }
  // }}}
  // T <arithmetic-operator> ModuloInteger {{{
  friend constexpr ModuloInteger operator+(integer a, ModuloInteger const &mv) {
    return ModuloInteger(a % mod + mv.val);
  }
  friend constexpr ModuloInteger operator-(integer a, ModuloInteger const &mv) {
    return ModuloInteger(a % mod - mv.val);
  }
  friend constexpr ModuloInteger operator*(integer a, ModuloInteger const &mv) {
    return ModuloInteger((mod + a % mod) * mv.val % mod, 0);
  }
  friend constexpr ModuloInteger operator/(integer a, ModuloInteger const &mv) {
    return ModuloInteger((mod + a % mod) * modinv(mv.val) % mod, 0);
  }
  // }}}
  // power {{{
  ModuloInteger operator^(integer x) const { return pow(*this, x); }
  ModuloInteger &operator^=(integer x) {
    val = modpow(val, x);
    return *this;
  }
  friend ModuloInteger pow(ModuloInteger x, integer y) {
    return ModuloInteger(modpow(x.val, y), 0);
  }
  // }}}
};
template < long long mod >
ModuloInteger< mod > ModuloInteger< mod >::unused(mod, 0);
/// }}}--- ///

using modint = ModuloInteger<>;

// NOTE : use H with larger N
/// --- Modulo Factorial {{{ ///
#include <cassert>
#include <cstddef>
template < std::size_t N, int mod = static_cast< int >(1e9 + 7) >
struct Factorial {
  using integer = long long;
  constexpr integer extgcd(integer a, integer b, integer &x, integer &y) {
    integer d = 0;
    return b == 0 ? (x = a < 0 ? -1 : 1, y = 0, a < 0 ? -a : a)
      : (d = extgcd(b, a % b, y, x), y -= a / b * x, d);
  }
  constexpr integer modinv(integer a) {
    integer x = 0, y = 0;
    extgcd(a, mod, x, y);
    if(x < 0)
      x += mod;
    else if(x == mod)
      x = 0;
    return x;
  }
  int arr[N + 1], inv[N + 1];
  integer operator[](int i) const { return arr[i]; }
  Factorial() : arr(), inv() {
    arr[0] = 1;
    for(std::size_t i = 1; i <= N; i++) {
      arr[i] = (integer) i * arr[i - 1] % mod;
    }
    inv[N] = modinv(arr[N]);
    for(int i = N - 1; i >= 0; i--) {
      inv[i] = (integer)(i + 1) * inv[i + 1] % mod;
    }
  }
  integer C(int n, int r) const {
    if(n < 0 || r < 0 || n < r) return 0;
    assert(n <= N);
    return (integer) arr[n] * inv[r] % mod * inv[n - r] % mod;
  }
  integer H(int n, int r) const { return C(n + r - 1, r); }
};
/// }}}--- ///

constexpr int mod = 1e9 + 7;
const int N = 1e5 + 10;
Factorial< N * 2, mod > fact;

int main() {
  std::ios::sync_with_stdio(false), std::cin.tie(0);
  int n, r;
  while(1) {
    cin >> n;
    if(!n) break;
    vector<int> v(n, 0);
    BIT<> bit(n);
    for(int i = 0; i < n; i++) bit.add(i, 1);
    iota(v.begin(), v.end(), 0);
    cin >> r;
    for(int i = 0; i < r; i++) {
      int a, b;
      cin >> a >> b;
      a--, b--;
      swap(v[a], v[b]);
    }
    modint ans = 0;
    for(int i = 0; i < n; i++) {
      bit.add(v[i], -1);
      ans += modint(bit.sum(v[i])) * fact[n - i - 1];
    }

    cout << ans << "\n";

  }
  return 0;
}