#include using namespace std; using i64 = int_fast64_t; using ui64 = uint_fast64_t; using db = long double; using pii = pair; using pli = pair; using pll = pair; using pdi = pair; template using vct = vector; template using heap = priority_queue; template using minheap = priority_queue, greater>; template constexpr T inf = numeric_limits::max() / 2 - 1; constexpr int dx[9] = {1, 0, -1, 0, 1, -1, -1, 1, 0}; constexpr int dy[9] = {0, 1, 0, -1, 1, 1, -1, -1, 0}; constexpr long double gold = 1.618033988; constexpr long double eps = 1e-15; #define mod 100000007LL #define stdout_precision 10 #define stderr_precision 2 #define each(i,v) for (auto i = begin(v); i != end(v); ++i) #define reach(i,v) for (auto i = rbegin(v); i != rend(v); ++i) #define urep(i,s,t) for (int i = (s); i <= (t); ++i) #define drep(i,s,t) for (int i = (s); i >= (t); --i) #define rep(i,n) urep(i, 0, (n)-1) #define rep1(i,n) urep(i, 1, (n)) #define rrep(i,n) drep(i, (n)-1, 0) #define all(v) begin(v), end(v) #define rall(v) rbegin(v), rend(v) #define fir first #define sec second #define fro front() #define bac back() #define u_map unordered_map #define u_set unordered_set #define l_bnd lower_bound #define u_bnd upper_bound #define rsz resize #define ers erase #define emp emplace #define emf emplace_front #define emb emplace_back #define pof pop_front #define pob pop_back #define mkp make_pair #define mkt make_tuple #define popcnt __builtin_popcount struct setupper { setupper() { ios::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); std::cerr.tie(nullptr); std::cout << fixed << setprecision(stdout_precision); std::cerr << fixed << setprecision(stderr_precision); #ifdef Local std::cerr << "\n---stderr---\n"; auto print_atexit = []() { std::cerr << "Exec time : " << clock() / (double)CLOCKS_PER_SEC * 1000.0 << "ms\n"; std::cerr << "------------\n"; }; atexit((void(*)())print_atexit); #endif } } setupper_; namespace std { template void hash_combine(size_t &seed, T const &key) { seed ^= hash()(key) + 0x9e3779b9 + (seed << 6) + (seed >> 2); } template struct hash> { size_t operator()(pair const &pr) const { size_t seed = 0; hash_combine(seed,pr.first); hash_combine(seed,pr.second); return seed; } }; template ::value - 1> struct hashval_calc { static void apply(size_t& seed, Tup const& tup) { hashval_calc::apply(seed, tup); hash_combine(seed,get(tup)); } }; template struct hashval_calc { static void apply(size_t& seed, Tup const& tup) { hash_combine(seed,get<0>(tup)); } }; template struct hash> { size_t operator()(tuple const& tup) const { size_t seed = 0; hashval_calc>::apply(seed,tup); return seed; } }; } template ostream& operator << (ostream& s, pair p) { return s << p.fir << " " << p.sec; } template ostream& operator << (ostream& s, vct v) { each(i,v) { if(i != begin(v)) s << " "; s << *i; } return s; } #define dump(...) cerr << " [ " << __LINE__ << " : " << __FUNCTION__ << " ] " << #__VA_ARGS__ << " : ";\ dump_func(__VA_ARGS__) template void dump_func(T x) { cerr << x << '\n'; } template void dump_func(T x, Rest ... rest) { cerr << x << ","; dump_func(rest...); } template T read() { T x; return cin >> x, x; } template void write(T x) { cout << x << '\n'; } template void write(T x, Rest ... rest) { cout << x << ' '; write(rest...); } void writeln() {} template void writeln(T x, Rest ... rest) { cout << x << '\n'; writeln(rest...); } #define esc(...) writeln(__VA_ARGS__), exit(0) namespace updater { template static void add(T &x, const T &y) { x += y; } template static void ext_add(T &x, const T &y, size_t w) { x += y * w; } template static void mul(T &x, const T &y) { x *= y; } template static void ext_mul(T &x, const T &y, size_t w) { x *= (T)pow(y,w); } template static bool chmax(T &x, const T &y) { return x < y ? x = y,true : false; } template static bool chmin(T &x, const T &y) { return x > y ? x = y,true : false; } }; using updater::chmax; using updater::chmin; template T minf(const T &x, const T &y) { return min(x,y); } template T mixf(const T &x, const T &y) { return max(x,y); } bool bit(i64 n, uint8_t e) { return (n >> e) & 1; } i64 mask(i64 n, uint8_t e) { return n & ((1 << e) - 1); } int ilog(uint64_t x, uint64_t b = 2) { return x ? 1 + ilog(x / b,b) : -1; } template int_fast64_t binry(int_fast64_t ok,int_fast64_t ng,const F &fn) { if(abs(ok - ng) <= 1) return ok; int_fast64_t mid = ok + ng >> 1; return fn(mid) ? binry(mid,ng,fn) : binry(ok,mid,fn); } template void init(A (&ary)[N], const T &val) { fill((T*)ary,(T*)(ary + N),val); } template void cmprs(A ary[], size_t n) { vector tmp(ary,ary + n); tmp.erase(unique(begin(tmp),end(tmp)), end(tmp)); for(A *i = ary; i != ary + n; ++i) *i = l_bnd(all(tmp),*i) - begin(tmp); } template void cmprs(vector &v) { vector tmp = v; sort(begin(tmp),end(tmp)); tmp.erase(unique(begin(tmp),end(tmp)), end(tmp)); for(auto i = begin(v); i != end(v); ++i) *i = l_bnd(all(tmp),*i) - begin(tmp); } namespace Calcfn { #ifndef mod #define mod 1000000007LL #endif struct Modint { int x; constexpr Modint() : x(0) {} constexpr Modint(uint_fast64_t y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {} constexpr Modint &operator+=(const Modint &p) { if((x += p.x) >= mod) x -= mod; return *this; } constexpr Modint &operator-=(const Modint &p) { if((x += mod - p.x) >= mod) x -= mod; return *this; } constexpr Modint &operator*=(const Modint &p) { x = (int) (1LL * x * p.x % mod); return *this; } constexpr Modint &operator/=(const Modint &p) { *this *= inverse(p); return *this; } constexpr Modint operator-() { return Modint(-x); } constexpr Modint operator+(const Modint &p) { return Modint(*this) += p; } constexpr Modint operator-(const Modint &p) { return Modint(*this) -= p; } constexpr Modint operator*(const Modint &p) { return Modint(*this) *= p; } constexpr Modint operator/(const Modint &p) { return Modint(*this) /= p; } constexpr bool operator==(const Modint &p) { return x == p.x; } constexpr bool operator!=(const Modint &p) { return x != p.x; } constexpr bool operator!() { return !x; } constexpr bool operator>(const Modint &p) { return x > p.x; } constexpr bool operator<(const Modint &p) { return x < p.x; } constexpr bool operator>=(const Modint &p) { return x >= p.x; } constexpr bool operator<=(const Modint &p) { return x <= p.x; } constexpr static Modint inverse(const Modint &p) { int a = p.x, b = mod, u = 1, v = 0; while(b > 0) { int t = a / b; a -= t * b; a ^= b ^= a ^= b; u -= t * v; u ^= v ^= u ^= v; } return Modint(u); } constexpr static Modint pow(Modint p, uint_fast64_t e) { Modint ret(1); while(e) { if(e & 1) ret *= p; p *= p; e >>= 1; } return ret; } friend ostream &operator<<(ostream &s, const Modint &p) { return s << p.x; } friend istream &operator>>(istream &s, Modint &p) { uint_fast64_t x; p = Modint((s >> x,x)); return s; } }; constexpr static uint N = 200007; struct impl { uint_fast64_t fact_[N + 1],invfact_[N + 1],inv_[N + 1]; constexpr impl() : fact_(),invfact_(),inv_() { fact_[0] = 1; for(int i = 1; i <= N; ++i) fact_[i] = fact_[i - 1] * i % mod; inv_[1] = 1; for(int i = 2; i <= N; ++i) inv_[i] = mod - inv_[mod % i] * (mod / i) % mod; invfact_[0] = 1; for(int i = 1; i <= N; ++i) invfact_[i] = invfact_[i - 1] * inv_[i] % mod; } }; constexpr static impl impl_exe; constexpr static Modint fact(int x) { return x >= 0 ? impl_exe.fact_[x] : 0; } constexpr static Modint invfact(int x) { return x >= 0 ? impl_exe.invfact_[x] : 0; } constexpr static Modint comb(int x, int y) { return fact(x) * invfact(y) * invfact(x - y); } constexpr static Modint perm(int x, int y) { return comb(x,y) * fact(y); } constexpr static int_fast64_t gcd(int_fast64_t a, int_fast64_t b) { if(!b) return a > 0 ? a : -a; return gcd(b, a % b); } constexpr static int_fast64_t lcm(int_fast64_t a, int_fast64_t b) { if(a | b) return a / gcd(a, b) * b; return 0; } constexpr static uint_fast64_t ext_gcd(uint_fast64_t a, uint_fast64_t b, int_fast64_t &x, int_fast64_t &y) { uint_fast64_t d = a; if (b) d = ext_gcd(b, a % b, y, x), y -= (a / b) * x; else x = 1, y = 0; return d; } constexpr static Modint modinv(uint_fast64_t x) { int_fast64_t z = 0,y = 0; ext_gcd(x,mod,z,y); return Modint(z); } constexpr static Modint modpow(Modint x, uint_fast64_t e) { if(!e) return 1; if(!x) return 0; return modpow(x * x, e >> 1) * (e & 1 ? x : 1); } } using Calcfn::Modint; using Calcfn::fact; using Calcfn::invfact; using Calcfn::comb; int n,h,w; pii frnd[24]; signed main() { cin>>h>>w>>n; rep(i,n) { cin>>frnd[i].fir>>frnd[i].sec; } for(int i=0; i<1< pos; for(int ii=0; ii>ii&1) pos.emb(frnd[ii]); } pos.emb(h,w); sort(all(pos)); int nn=pos.size(); Modint dp[23]={}; for(int j=0; j