#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define rep(i,n) for(int i=0;i<n;i++)
#define all(v) v.begin(),v.end()
#define pb push_back
#define eb emplace_back
template<class T>void chmax(T &a,T b){if(a<b)a=b;}
template<class T>void chmin(T &a,T b){if(a>b)a=b;}
constexpr int INF=1000000000;
constexpr ll llINF=1000000000000000000;
constexpr int mod=1000000007;
constexpr double eps=1e-8;
const double pi=acos(-1);
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
int Random(int mi,int ma){
    random_device rnd;
    mt19937 mt(rnd());//32bit
    //[mi,ma]
    uniform_int_distribution<int>engine(mi,ma);
    return engine(mt);
}
ll gcd(ll a,ll b){
    if(b==0)return a;
    return gcd(b,a%b);
}
ll lcm(ll a,ll b){
    return a/gcd(a,b)*b;
}
bool prime(int a){
    if(a==1)return false;
    for(int i=2;i*i<=a;i++){
        if(a%i==0)return false;
    }
    return true;
}
ll modpow(ll a,ll b){
    if(b==0)return 1;
    if(b%2)return modpow(a,b-1)*a%mod;
    ll memo=modpow(a,b/2);
    return memo*memo%mod;
}
vector<ll>kaijo,invkaijo;
void init_fact(int n){
    kaijo.resize(n+1);
    invkaijo.resize(n+1);
    kaijo[0]=1;
    for(ll i=1;i<=n;i++){
        kaijo[i]=kaijo[i-1]*i;
        kaijo[i]%=mod;
    }
    rep(i,n+1)invkaijo[i]=modpow(kaijo[i],mod-2);
}
/*
vector<vector<ll>>C,sC;
void init_comb(int n,int m){
    C.resize(n+1,vector<ll>(m+1,0));
    sC.resize(n+1,vector<ll>(m+1,0));
    C[0][0]=1;
    for(int i=1;i<=n;i++){
        C[i][0]=1;
        for(int j=1;j<=m;j++){
            C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
        }
    }
    rep(i,n+1){
        rep(j,m){
            sC[i][j+1]=(sC[i][j]+C[i][j])%mod;
        }
    }
}*/
ll comb(int a,int b){
    if(a<b)return 0;
    if(a<0)return 0;
    return kaijo[a]*invkaijo[a-b]%mod*invkaijo[b]%mod;
}
ll inv(ll x){
    x=modpow(x,mod-2);
    return x;
}
struct BIT{
    int n,beki=1;
    vector<int>bit;
    BIT(int x){
        bit.resize(x+1,0);
        n=x;
        while(beki*2<=n)beki*=2;
    }
    int sum(int i){
        int res=0;
        while(i>0){
            res+=bit[i];
            i-=i&-i;
        }
        return res;
    }
    int sum(int l,int r){
        //[l,r]
        return sum(r)-(l==0?0:sum(l-1));
    }
    void add(int i,int x){
        while(i<=n){
            bit[i]+=x;
            i+=i&-i;
        }
    }
    void add(int l,int r,int x){
        //[l,r]+=x
        add(l,x);
        if(r<n)add(r+1,-x);
    }
    int lowerbound(int w){
        if(w<=0)return 0;
        int x=0;
        for(int k=beki;k>0;k>>=1){
            if(x+k<=n&&bit[x+k]<w){
                w-=bit[x+k];
                x+=k;
            }
        }
        return x+1;
    }
};
int h,w,m;
vector<int>G[200010];
int main(){
    cin>>h>>w>>m;
    int mi=h-1,mj=w;
    rep(i,m){
        int x,y;
        cin>>x>>y;
        x--;
        if(x==0)chmin(mj,y-1);
        else{
            if(y==1)chmin(mi,x-1);
            G[x].pb(y);
        }
    }
    BIT bit(w);
    ll ans=0;
    rep(i,h){
        if(i==0){
            ans+=mj;
            continue;
        }
        for(int j:G[i]){
            if(bit.sum(j,j)==0)bit.add(j,1);
        }
        if(i<=mi){
            int mjn=w;
            for(int j:G[i]){
                chmin(mjn,j-1);
            }
            ans+=mjn;
            if(mjn+1<=mj)ans+=(mj-mjn)-bit.sum(mjn+1,mj);
        }
        else{
            ans+=mj-bit.sum(1,mj);
        }
    }
    cout<<ans<<endl;
    return 0;
}
#include<bits/stdc++.h>
#define endl '\n'
#define mp make_pair
#define pb push_back
#define ll long long
#define pii pair<int,int>
#define sz(x) (int)(x).size()
#define all(x) (x).begin(),(x).end()
#define mem(a,b) memset(a,b,sizeof(a))
char *fs,*ft,buf[1<<20];
#define gc() (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<20,stdin),fs==ft))?0:*fs++;
inline int read()
{
    int x=0,f=1;
    char ch=gc();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            f=-1;
        ch=gc();
    }
    while(ch>='0'&&ch<='9')
    {
        x=x*10+ch-'0';
        ch=gc();
    }
    return x*f;
}
using namespace std;
#define int long long
const int mod = 1e9+7;
const int INF = 0x3f3f3f3f;
const int N = 2e5+10;

string a="0123456789ABCDEF",s;
int k,f[N][17];
int dfs(int pos,int st,int lim,int pre,int cnt)
{
    if(pos==sz(s)) return (cnt==k);
    if(!lim&&f[pos][cnt]!=-1&&!st) return f[pos][cnt];
    char high = lim?s[pos]:'F';
    int res=0;
    for(int i=0;i<sz(a);i++)
    {
        if(st&&i==0)
            res = (res+dfs(pos+1,st&&i==0,lim&&a[i]==high,pre,cnt))%mod;
        else
            res = (res+dfs(pos+1,st&&i==0,lim&&a[i]==high,pre|(1<<i),cnt+(pre!=(pre|(1<<i)))))%mod;
        if(a[i]==high) break;
    }
    if(!lim&&!st) f[pos][cnt] = res;
    return res;
}
signed main()
{
    cin>>s>>k;
    mem(f,-1);
    cout<<dfs(0,1,1,0,0)<<endl;
}
