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

Solution (in CPP):

Solution:
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"
#include "numeric"
#include "cassert"

using namespace std;

const long long int MOD = 1000000007;
//const int MOD = 998244353;

long long int N, M, K, H, W, L, R;
//int N, M, K, H, W, L, R


int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> N >> M >> K;
	if (M % 7) {
		vector<int>box(M);
		for (int i = 0; i < K; i++) {
			cin >> L;
			box[L] = 1;
		}
		vector<vector<int>>v(M * 2, vector<int>(7));
		for (int i = 0; i < M * 2; i++) {
			for (int j = 0; j < 7; j++) {
				v[i][j] = box[(i * 7 + j) % M];
			}
		}
		int dir[] = { 1,0,-1,0,1 };
		long long int a = 0, b = 0;
		queue<pair<int, int>>Q;
		for (int i = 0; i < M; i++) {
			for (int j = 0; j < 7; j++) {
				if (v[i][j])continue;
				a++;
				Q.push({ i,j });
				v[i][j] = MOD;
				while (!Q.empty()) {
					int y = Q.front().first;
					int x = Q.front().second;
					Q.pop();
					for (int k = 0; k < 4; k++) {
						int ny = y + dir[k];
						int nx = x + dir[k + 1];
						if (ny < 0 || nx < 0 || ny >= M || nx >= 7)continue;
						if (v[ny][nx])continue;
						v[ny][nx] = MOD;
						Q.push({ ny,nx });
					}
				}
			}
		}
		for (auto &i : v) {
			for (auto &j : i)j %= MOD;
		}
		M <<= 1;
		for (int i = 0; i < M; i++) {
			for (int j = 0; j < 7; j++) {
				if (v[i][j])continue;
				b++;
				Q.push({ i,j });
				v[i][j] = MOD;
				while (!Q.empty()) {
					int y = Q.front().first;
					int x = Q.front().second;
					Q.pop();
					for (int k = 0; k < 4; k++) {
						int ny = y + dir[k];
						int nx = x + dir[k + 1];
						if (ny < 0 || nx < 0 || ny >= M || nx >= 7)continue;
						if (v[ny][nx])continue;
						v[ny][nx] = MOD;
						Q.push({ ny,nx });
					}
				}
			}
		}
		b -= a;
		a += ((N * 2 / M) - 1)*b;
		cout << a << endl;
	}
	else {
		vector<int>box(M);
		for (int i = 0; i < K; i++) {
			cin >> L;
			box[L] = 1;
		}
		vector<vector<int>>v(M * 2 / 7, vector<int>(7));
		for (int i = 0; i < M * 2 / 7; i++) {
			for (int j = 0; j < 7; j++) {
				v[i][j] = box[(i * 7 + j) % M];
			}
		}
		int dir[] = { 1,0,-1,0,1 };
		long long int a = 0, b = 0;
		queue<pair<int, int>>Q;
		for (int i = 0; i < M / 7; i++) {
			for (int j = 0; j < 7; j++) {
				if (v[i][j])continue;
				a++;
				Q.push({ i,j });
				v[i][j] = MOD;
				while (!Q.empty()) {
					int y = Q.front().first;
					int x = Q.front().second;
					Q.pop();
					for (int k = 0; k < 4; k++) {
						int ny = y + dir[k];
						int nx = x + dir[k + 1];
						if (ny < 0 || nx < 0 || ny >= M / 7 || nx >= 7)continue;
						if (v[ny][nx])continue;
						v[ny][nx] = MOD;
						Q.push({ ny,nx });
					}
				}
			}
		}
		for (auto &i : v) {
			for (auto &j : i)j %= MOD;
		}
		M <<= 1;
		for (int i = 0; i < M / 7; i++) {
			for (int j = 0; j < 7; j++) {
				if (v[i][j])continue;
				b++;
				Q.push({ i,j });
				v[i][j] = MOD;
				while (!Q.empty()) {
					int y = Q.front().first;
					int x = Q.front().second;
					Q.pop();
					for (int k = 0; k < 4; k++) {
						int ny = y + dir[k];
						int nx = x + dir[k + 1];
						if (ny < 0 || nx < 0 || ny >= M / 7 || nx >= 7)continue;
						if (v[ny][nx])continue;
						v[ny][nx] = MOD;
						Q.push({ ny,nx });
					}
				}
			}
		}
		b -= a;
		a += ((N * 14 / M) - 1)*b;
		cout << a << endl;
	}
	return 0;
}