#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
#include <fstream>
#define popcount __builtin_popcount
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
int par[700002];
int rk[700002];

void init(int n){
	for(int i=0; i<n; i++){
		par[i]=i;
	}
}
 
int find(int x){
	if(par[x]==x){
		return x;
	}else{
		return par[x]=find(par[x]);
	}
}
 
void unite(int x, int y){
	x=find(x);
	y=find(y);
	if(x==y) return;
	if(rk[x]<rk[y]){
		par[x]=y;
	}else{
		par[y]=x;
		if(rk[x]==rk[y]) rk[x]++;
	}
}
 
bool same(int x, int y){
	return find(x)==find(y);
}

ll n; int m, q;
int p1[7], p2[7];
bool b[700001];
ll conn(int p1a[7], int p2a[7], int p1b[7], int p2b[7], int p1c[7], int p2c[7]){
    init(28);
    for(int i=0; i<14; i++){
        if((i<7 && !b[i]) || (i>=7 && !b[m-7+i-7])) continue;
        for(int j=i+1; j<14; j++){
            if((j<7 && !b[j]) || (j>=7 && !b[m-7+j-7])) continue;
            int x, y;
            if(i<7) x=p1a[i];
            else x=p2a[i-7];
            if(j<7) y=p1a[j];
            else y=p2a[j-7];
            if(x==y) unite(i, j);
            if(i<7) x=p1b[i];
            else x=p2b[i-7];
            if(j<7) y=p1b[j];
            else y=p2b[j-7];
            if(x==y) unite(i+14, j+14);
        }
    }
    for(int i=0; i<7; i++){
        if(b[i] && b[m-7+i]) unite(i+7, i+14);
    }
    set<int> st;
    for(int i=0; i<28; i++){
        if((i<7 && !b[i]) || (7<=i && i<14 && !b[m-7+i-7]) || (14<=i && i<21 && !b[i-14]) || (i>=21 && !b[m-7+i-21])) continue;
        st.insert(find(i));
    }
    for(int i=0; i<7; i++){
        p1c[i]=find(i);
        st.erase(p1c[i]);
    }
    for(int i=0; i<7; i++){
        p2c[i]=find(i+21);
        st.erase(p2c[i]);
    }
    return st.size();
}
ll ct;
ll pow(ll k){
    int p1p[7], p2p[7], p1a[7], p2a[7];
    for(int i=0; i<7; i++) p1p[i]=p1[i], p2p[i]=p2[i];
    bool mada=1;
    ll ans=0;
    while(k){
        if(k&1){
            if(mada){
                for(int i=0; i<7; i++) p1a[i]=p1p[i], p2a[i]=p2p[i];
              ans+=ct;
                mada=0;
            }else{
                int p1c[7], p2c[7];
                ans+=conn(p1p, p2p, p1a, p2a, p1c, p2c);
                ans+=ct;
                for(int i=0; i<7; i++) p1a[i]=p1c[i], p2a[i]=p2c[i];
            }
        }
        int p1c[7], p2c[7];
        ct=2*ct+conn(p1p, p2p, p1p, p2p, p1c, p2c);
        for(int i=0; i<7; i++) p1p[i]=p1c[i], p2p[i]=p2c[i];
        k>>=1;
    }
    set<int> st;
    for(int i=0; i<7; i++){
        if(b[i]) st.insert(p1a[i]);
        if(b[m-7+i]) st.insert(p2a[i]);
    }
    ans+=(ll)st.size();
    return ans;
}
int main()
{
    cin>>n>>m>>q;
    int a[100001];
    for(int i=0; i<q; i++){
        cin>>a[i];
    }
    if(m%7!=0){
        m*=7;
        fill(b, b+m, 1);
        for(int i=0; i<q; i++){
            for(int j=0; j<7; j++){
                b[a[i]+m/7*j]=0;
            }
        }
    }else{
        fill(b, b+m, 1);
        for(int i=0; i<q; i++) b[a[i]]=0;
    }
    init(m);
    for(int i=0; i<m; i++){
        if(!b[i]) continue;
        if(i%7!=0 && b[i-1]) unite(i-1, i);
        if(i>=7 && b[i-7]) unite(i-7, i);
    }
    set<int> st;
    for(int i=0; i<m; i++){
        if(!b[i]) continue;
        st.insert(find(i));
    }
    for(int i=0; i<7; i++){
        p1[i]=find(i);
        st.erase(p1[i]);
    }
    for(int i=0; i<7; i++){
        p2[i]=find(m-7+i);
        st.erase(p2[i]);
    }
    ct=st.size();
    cout<<pow(7*n/(ll)m)<<endl;
    return 0;
}
### Prompt

Develop a solution in cpp to the problem described below:

Input Format

The input format is following:



n m q
a_1 a_2 ... a_q


Output Format

Print the number of connected part in one line.


Constraints

* n ≤ 10^{12}
* 7n is divisible by m.
* 1 ≤ q ≤ m ≤ 10^5
* 0 ≤ a_1 < a_2 < ... < a_q < m



Scoring

Subtask 1 [100 points]


* n ≤ 100000.

Subtask 2 [90 points]


* m is divisible by 7.
* a_{i + 1} - a_i = 1.

Subtask 3 [200 points]


* m is divisible by 7.

Subtask 4 [110 points]


* There are no additional constraints.



Sample Input 1


7 7 3
1 3 5


Sample Output 1


4


The calendar looks like this:


<image>

Sample Input 2


10 14 8
5 6 7 8 9 10 11 12


Sample Output 2


10


The calendar looks like this:


<image>

Output Format

Print the number of connected part in one line.


Constraints

* n ≤ 10^{12}
* 7n is divisible by m.
* 1 ≤ q ≤ m ≤ 10^5
* 0 ≤ a_1 < a_2 < ... < a_q < m



Scoring

Subtask 1 [100 points]


* n ≤ 100000.

Subtask 2 [90 points]


* m is divisible by 7.
* a_{i + 1} - a_i = 1.

Subtask 3 [200 points]


* m is divisible by 7.

Subtask 4 [110 points]


* There are no additional constraints.

Input Format

The input format is following:



n m q
a_1 a_2 ... a_q

Examples

Input

7 7 3
1 3 5


Output

4


Input

10 14 8
5 6 7 8 9 10 11 12


Output

10

### Response

```cpp
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
#include <fstream>
#define popcount __builtin_popcount
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
int par[700002];
int rk[700002];

void init(int n){
	for(int i=0; i<n; i++){
		par[i]=i;
	}
}
 
int find(int x){
	if(par[x]==x){
		return x;
	}else{
		return par[x]=find(par[x]);
	}
}
 
void unite(int x, int y){
	x=find(x);
	y=find(y);
	if(x==y) return;
	if(rk[x]<rk[y]){
		par[x]=y;
	}else{
		par[y]=x;
		if(rk[x]==rk[y]) rk[x]++;
	}
}
 
bool same(int x, int y){
	return find(x)==find(y);
}

ll n; int m, q;
int p1[7], p2[7];
bool b[700001];
ll conn(int p1a[7], int p2a[7], int p1b[7], int p2b[7], int p1c[7], int p2c[7]){
    init(28);
    for(int i=0; i<14; i++){
        if((i<7 && !b[i]) || (i>=7 && !b[m-7+i-7])) continue;
        for(int j=i+1; j<14; j++){
            if((j<7 && !b[j]) || (j>=7 && !b[m-7+j-7])) continue;
            int x, y;
            if(i<7) x=p1a[i];
            else x=p2a[i-7];
            if(j<7) y=p1a[j];
            else y=p2a[j-7];
            if(x==y) unite(i, j);
            if(i<7) x=p1b[i];
            else x=p2b[i-7];
            if(j<7) y=p1b[j];
            else y=p2b[j-7];
            if(x==y) unite(i+14, j+14);
        }
    }
    for(int i=0; i<7; i++){
        if(b[i] && b[m-7+i]) unite(i+7, i+14);
    }
    set<int> st;
    for(int i=0; i<28; i++){
        if((i<7 && !b[i]) || (7<=i && i<14 && !b[m-7+i-7]) || (14<=i && i<21 && !b[i-14]) || (i>=21 && !b[m-7+i-21])) continue;
        st.insert(find(i));
    }
    for(int i=0; i<7; i++){
        p1c[i]=find(i);
        st.erase(p1c[i]);
    }
    for(int i=0; i<7; i++){
        p2c[i]=find(i+21);
        st.erase(p2c[i]);
    }
    return st.size();
}
ll ct;
ll pow(ll k){
    int p1p[7], p2p[7], p1a[7], p2a[7];
    for(int i=0; i<7; i++) p1p[i]=p1[i], p2p[i]=p2[i];
    bool mada=1;
    ll ans=0;
    while(k){
        if(k&1){
            if(mada){
                for(int i=0; i<7; i++) p1a[i]=p1p[i], p2a[i]=p2p[i];
              ans+=ct;
                mada=0;
            }else{
                int p1c[7], p2c[7];
                ans+=conn(p1p, p2p, p1a, p2a, p1c, p2c);
                ans+=ct;
                for(int i=0; i<7; i++) p1a[i]=p1c[i], p2a[i]=p2c[i];
            }
        }
        int p1c[7], p2c[7];
        ct=2*ct+conn(p1p, p2p, p1p, p2p, p1c, p2c);
        for(int i=0; i<7; i++) p1p[i]=p1c[i], p2p[i]=p2c[i];
        k>>=1;
    }
    set<int> st;
    for(int i=0; i<7; i++){
        if(b[i]) st.insert(p1a[i]);
        if(b[m-7+i]) st.insert(p2a[i]);
    }
    ans+=(ll)st.size();
    return ans;
}
int main()
{
    cin>>n>>m>>q;
    int a[100001];
    for(int i=0; i<q; i++){
        cin>>a[i];
    }
    if(m%7!=0){
        m*=7;
        fill(b, b+m, 1);
        for(int i=0; i<q; i++){
            for(int j=0; j<7; j++){
                b[a[i]+m/7*j]=0;
            }
        }
    }else{
        fill(b, b+m, 1);
        for(int i=0; i<q; i++) b[a[i]]=0;
    }
    init(m);
    for(int i=0; i<m; i++){
        if(!b[i]) continue;
        if(i%7!=0 && b[i-1]) unite(i-1, i);
        if(i>=7 && b[i-7]) unite(i-7, i);
    }
    set<int> st;
    for(int i=0; i<m; i++){
        if(!b[i]) continue;
        st.insert(find(i));
    }
    for(int i=0; i<7; i++){
        p1[i]=find(i);
        st.erase(p1[i]);
    }
    for(int i=0; i<7; i++){
        p2[i]=find(m-7+i);
        st.erase(p2[i]);
    }
    ct=st.size();
    cout<<pow(7*n/(ll)m)<<endl;
    return 0;
}
```