#include<bits/stdc++.h>
#define ll long long
using namespace std;

ll n; int m,cnt,a[4][7],b[35],fa[35]; bool bo[100005];
struct node{ int p[2][7]; ll sz; };
int getfa(int x){ return (x==fa[x])?x:fa[x]=getfa(fa[x]); }
node mrg(node u,node v){//puts("?");
	node ans; ans.sz=u.sz+v.sz;
	int i,j,cnt=0,mx=0;
	for (i=0; i<2; i++)
		for (j=0; j<7; j++) if (u.p[i][j]){
			a[i][j]=u.p[i][j]; mx=max(mx,a[i][j]);
		} else a[i][j]=0;
	for (i=0,cnt=mx; i<2; i++)
		for (j=0; j<7; j++) if (v.p[i][j]){
			a[i+2][j]=v.p[i][j]+mx; cnt=max(cnt,a[i+2][j]);
		} else a[i+2][j]=0;
	//for (i=0; i<4; i++)
	//	for (j=0; j<7; j++) printf("%d%c",a[i][j],(j==6)?'\n':' ');
	//		cout<<cnt<<endl;
	ans.sz-=cnt;
	for (i=1; i<=cnt; i++) fa[i]=i;
	for (i=0; i<7; i++){
		if (a[1][i] && a[2][i]) fa[getfa(a[1][i])]=getfa(a[2][i]);
	}
	memset(b,0,sizeof(b));
	for (i=cnt=0; i<7; i++){
		if (a[0][i]){
			if (!b[getfa(a[0][i])]) b[getfa(a[0][i])]=++cnt;
			ans.p[0][i]=b[getfa(a[0][i])];
		} else ans.p[0][i]=0;
		if (a[3][i]){
			if (!b[getfa(a[3][i])]) b[getfa(a[3][i])]=++cnt;
			ans.p[1][i]=b[getfa(a[3][i])];
		} else ans.p[1][i]=0;
	}
	for (i=0; i<7; i++){
		if (a[1][i] && !b[getfa(a[1][i])]){
			b[getfa(a[1][i])]=++cnt;
		}
		if (a[2][i] && !b[getfa(a[2][i])]){
			b[getfa(a[2][i])]=++cnt;
		}
		
	}
	//puts("!");
	ans.sz+=cnt;
	//cout<<ans.sz<<endl;
	//for (i=0; i<2; i++)
	//	for (j=0; j<7; j++) printf("%d%c",ans.p[i][j],(j<6)?' ':'\n');
	return ans;
}
node calc(ll i){
	int j,cnt=0; node u;
	for (j=0; j<7; j++) if (bo[(i*7+j)%m]){
		if (!j || !u.p[0][j-1]) cnt++;
		u.p[0][j]=u.p[1][j]=cnt;
	} else u.p[0][j]=u.p[1][j]=0;
	u.sz=cnt; return u;
}
node work(ll k){
	node ans=calc(0); int i;
	for (i=1; i<7*m; i++) ans=mrg(ans,calc(i));
	node x=ans; k--;
	for (; k; k>>=1,x=mrg(x,x)) if (k&1) ans=mrg(ans,x);
	return ans;
}
int main(){
	scanf("%lld%d%d",&n,&m,&cnt);
	if (!n){ puts("0"); return 0; }
	int i,x;
	memset(bo,1,sizeof(bo));
	for (i=1; i<=cnt; i++){
		scanf("%d",&x); bo[x]=0;
	}
	if (n<7*m){
		node ans=calc(0);
		for (i=1; i<n; i++) ans=mrg(ans,calc(i));
		printf("%lld\n",ans.sz);
		return 0;
	}
	node ans=work(n/(7*m));
	ll j;
	for (j=n/(7*m)*(7*m); j<n; j++) ans=mrg(ans,calc(j));
	printf("%lld\n",ans.sz);
	return 0;
}

### Prompt

Create a solution in Cpp for the following problem:

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<bits/stdc++.h>
#define ll long long
using namespace std;

ll n; int m,cnt,a[4][7],b[35],fa[35]; bool bo[100005];
struct node{ int p[2][7]; ll sz; };
int getfa(int x){ return (x==fa[x])?x:fa[x]=getfa(fa[x]); }
node mrg(node u,node v){//puts("?");
	node ans; ans.sz=u.sz+v.sz;
	int i,j,cnt=0,mx=0;
	for (i=0; i<2; i++)
		for (j=0; j<7; j++) if (u.p[i][j]){
			a[i][j]=u.p[i][j]; mx=max(mx,a[i][j]);
		} else a[i][j]=0;
	for (i=0,cnt=mx; i<2; i++)
		for (j=0; j<7; j++) if (v.p[i][j]){
			a[i+2][j]=v.p[i][j]+mx; cnt=max(cnt,a[i+2][j]);
		} else a[i+2][j]=0;
	//for (i=0; i<4; i++)
	//	for (j=0; j<7; j++) printf("%d%c",a[i][j],(j==6)?'\n':' ');
	//		cout<<cnt<<endl;
	ans.sz-=cnt;
	for (i=1; i<=cnt; i++) fa[i]=i;
	for (i=0; i<7; i++){
		if (a[1][i] && a[2][i]) fa[getfa(a[1][i])]=getfa(a[2][i]);
	}
	memset(b,0,sizeof(b));
	for (i=cnt=0; i<7; i++){
		if (a[0][i]){
			if (!b[getfa(a[0][i])]) b[getfa(a[0][i])]=++cnt;
			ans.p[0][i]=b[getfa(a[0][i])];
		} else ans.p[0][i]=0;
		if (a[3][i]){
			if (!b[getfa(a[3][i])]) b[getfa(a[3][i])]=++cnt;
			ans.p[1][i]=b[getfa(a[3][i])];
		} else ans.p[1][i]=0;
	}
	for (i=0; i<7; i++){
		if (a[1][i] && !b[getfa(a[1][i])]){
			b[getfa(a[1][i])]=++cnt;
		}
		if (a[2][i] && !b[getfa(a[2][i])]){
			b[getfa(a[2][i])]=++cnt;
		}
		
	}
	//puts("!");
	ans.sz+=cnt;
	//cout<<ans.sz<<endl;
	//for (i=0; i<2; i++)
	//	for (j=0; j<7; j++) printf("%d%c",ans.p[i][j],(j<6)?' ':'\n');
	return ans;
}
node calc(ll i){
	int j,cnt=0; node u;
	for (j=0; j<7; j++) if (bo[(i*7+j)%m]){
		if (!j || !u.p[0][j-1]) cnt++;
		u.p[0][j]=u.p[1][j]=cnt;
	} else u.p[0][j]=u.p[1][j]=0;
	u.sz=cnt; return u;
}
node work(ll k){
	node ans=calc(0); int i;
	for (i=1; i<7*m; i++) ans=mrg(ans,calc(i));
	node x=ans; k--;
	for (; k; k>>=1,x=mrg(x,x)) if (k&1) ans=mrg(ans,x);
	return ans;
}
int main(){
	scanf("%lld%d%d",&n,&m,&cnt);
	if (!n){ puts("0"); return 0; }
	int i,x;
	memset(bo,1,sizeof(bo));
	for (i=1; i<=cnt; i++){
		scanf("%d",&x); bo[x]=0;
	}
	if (n<7*m){
		node ans=calc(0);
		for (i=1; i<n; i++) ans=mrg(ans,calc(i));
		printf("%lld\n",ans.sz);
		return 0;
	}
	node ans=work(n/(7*m));
	ll j;
	for (j=n/(7*m)*(7*m); j<n; j++) ans=mrg(ans,calc(j));
	printf("%lld\n",ans.sz);
	return 0;
}

```