#ifndef VS
#include<bits/stdc++.h>
#endif

using namespace std;
typedef long long LL;

#ifdef BTK
#define DEBUG if(1)
#else
#define CIN_ONLY if(1)
struct cww {cww() {CIN_ONLY{ios::sync_with_stdio(false); cin.tie(0);}}
}star;
#define DEBUG if(0)
#endif

#define ALL(v) (v).begin(),(v).end()
#define REC(ret, ...) std::function<ret (__VA_ARGS__)>
template <typename T>inline bool chmin(T &l, T r){bool a = l>r; if (a)l = r; return a;}
template <typename T>inline bool chmax(T &l, T r){bool a = l<r; if (a)l = r; return a;}
template <typename T>istream& operator>>(istream &is, vector<T> &v){for (auto &it : v)is >> it;return is;}

class range {private: struct I { int x; int operator*() { return x; }bool operator!=(I& lhs) { return x<lhs.x; }void operator++() { ++x; } }; I i, n;public:range(int n) :i({ 0 }), n({ n }) {}range(int i, int n) :i({ i }), n({ n }) {}I& begin() { return i; }I& end() { return n; }};
template <typename ITR>
bool next_value(int base, ITR bg, ITR ed) {
	int c = 1;
	for (; bg != ed && c == 1; ++bg) {
		(*bg) += c;
		if ((c = ((*bg) == base)))(*bg) = 0;
	}
	return !c;
}

void rot(vector<int> &v) {
	int n = v.size();
	for (int i : range(n - 1)) {
		swap(v[i], v[i + 1]);
	}
}
LL naive(LL N,LL K) {
	set<vector<int>> s;
	vector<int> v(N, 0);
	do {
		auto u = v;
		reverse(ALL(u));
		bool ok = true;
		for (int i : range((int)N)) {
			if (v[i]!=u[i]) {
				ok = false;
			}
		}
		if(ok)for (int i : range((int)N)) {
			s.insert(u);
			rot(u);
		}
	} while (next_value(K, ALL(v)));
	return s.size();
}


namespace testcase {

	constexpr int LIM = 8;
	LL N, K;
	LL in[2] = { 7ll,1ll };
	bool generate() {
		N = in[0] + 1;
		K = in[1] + 1;
		bool ret = next_value(LIM, in, in + 2);
		return ret;
	}
	bool input() {
		DEBUG{
			return generate();
		}
		else {
			return !!(cin >> N >> K);
		}
	}

	void output(LL ret) {
		DEBUG{
				cout << N << " " << K;
				LL expected_answer = naive(N, K);
				if (ret == expected_answer) {
					cout << ": OK(" << ret << ")" << endl;
				}
				else {
					cout << ": NG" << endl;
					cout << " expected:" << expected_answer << endl;
					cout << " received:" << ret << endl;
					exit(0);
				}
		}
		else {
			cout << ret << endl;
		}
	}
}

constexpr int mod = 1e9 + 7;
LL divisor[112345];
LL dp[112345];
LL pow_mod(LL a, LL n, int M = mod) {
	LL res = 1;
	a %= M;
	while (n) {
		if (n & 1)
			res = (res*a) % M;
		a = (a*a) % M;
		n >>= 1;
	}
	return res;
}


inline LL invMod(LL a, LL m = mod) {
	LL b = m, u = 1, v = 0;
	while (b) {
		LL t = a / b;
		swap(a -= t * b, b);
		swap(u -= t * v, v);
	}
	return (u % m + m) % m;
}

LL solve() {
	LL N = testcase::N;
	LL K = testcase::K;
	int m = 0;
	for (LL d = 1; d*d <= N; d++) {
		if (N%d == 0) {
			divisor[m++] = d;
			divisor[m++] = N / d;
		}
	}
	sort(divisor, divisor + m);
	m = unique(divisor, divisor + m) - divisor;
	LL i2 = invMod(2);
	for (int i : range(m)) {
		const LL len = divisor[i] / 2;
		LL& latte = dp[i];
		if (divisor[i] % 2 == 0) {
			latte = pow_mod(K, len) * divisor[i] % mod;
		}
		else {
			latte = pow_mod(K, len + 1) * divisor[i] % mod;
		}
		for(int j:range(i)){
			if (divisor[i] % divisor[j] == 0) {
				LL malta = divisor[i] / divisor[j];
				latte += mod - dp[j] * malta % mod;
			}
		}
		latte %= mod;
	}
	LL ret = 0;
	for (int i : range(m)) {
		LL x = 1;
		if (divisor[i] % 2 == 0)x = i2;
		ret += dp[i]*x%mod;
	}
	return ret%mod;
}
int main() {
	while (testcase::input()) {
		LL ret = solve();
		testcase::output(ret);
	}
	return 0;
}


Measured memory_bytes: 256