/*!|||||||!!!!!!!!!!!!!!!!!!|%%$&&&&&&&&&&&&&|'`......```':'':!;.  ......````':!;..
||||||||||||!!!!!!!!!!!!!!!!!!!;;;;;!|%$$&&&|'..  ....``'''''::`  ......`````';:.
||||||||||||||||||||||!!!!!!!!!!;;;;;;;;;;;'`..  ....``'''''':` ........````':'.
|||||||||%%||%%|||||||||||||||||!;;;;;;;;'....   ....`````'''`..........````''.
%%%%%%%%%%%%%%%%%%|%||||%%|%%%%|!;!;;;;:.       ....```````'::'`........`````.
$$$$$$$%%$%%$$$$$%%%%%%%%%%%%%%|!!!!;'.        ....````````';|!!!!:`....```..
$$$$$$%%%$%%$$$$$%%%%%%%%%%%%%%!;!!;`          ....```````':!!!!!!!!|||;'`.
$$$%$%|%%||%%%%%%%%%%||%%%%%|%|!;!!:.         ....````````:!;;;!;;!!|%$$$$|:`
%%%%%||||||||||||||||||||||||||!;!;'`.        ....```````';!!!!!!!!||;';%$&@@%:`.
|||||||||!!|||||||||||||||||||!;!!:':'.       ..```''```';!!!!!!!||%$$%!` .'|&@@%:`. .
||||||||!!!|||||||||||||||||||!;!;::;;:`     ..````'''`';;!!!!!!|%%$$$$&&%'   .;&#@!'....
|||||||!!!!|||||||||||||||||||!;!;:;;;;;'.  ..```''''`:!!!!!;!!|%$$$$&&&&&@$:.   .;&#$:....
|||!||||!!||||||||||||||||||||!;!::;;;;;;;`..```''':':;!!!!!!!!|%$$&&&&&&@&@#$:.   .`!@$:...
|||!|||!!!|||||||||||||||||||!!;;:;;;;;;;!!;'`'''':':!;;;;;!!|||||%$&&&&@@@@@@@%`......:$$:...
||!!||!!!!!||||||||||||||||||!!;;:;;;;;;;!!|!;'''``'':;!!;!!;!|$$$%|%&&&@@@@@@@#&;.......'%|`..
||!!||!!!!!!|||||||||||||||!!!!;;:;;;;;;:''::::;;!;;;;':!!!!!!!!!%$&$|%&@@@@@@#@@&!`.......`|;..
||!!|!!!!!!!||||||||||||||||||!;;:;;'````:!%%%%|;:;;:::::;|!!||!!!!|$&$%%&@@&@@##@&!'........;|'.
|!!!|!!!!!!!|||||||||||||||!!!!;:'```';!!||!!!|!!;;;;:::::;%%||%%|||||%&$%%&@@@@@##&;`` ......'!:.
|!!!!!!!!!!!!|||||||||||||!!!!!;::;;;;;:;!!!|||||!!;;;;;;;;!%$%|%$$%||||%$$%$&@@@@#@$:``      .`''.
|!!!||!!!!!!!||||||||||||!!!!!!!;;;:::;;!!|||||||||!!;;;;;;;;|$%|%%$$$%|||%%$$&@&@@#@!.`'.     ...`.
|!!!||!!!!!!!||||||||||||!!!!!!!;:;;;;;!!!!!|||||||||!!;;;;;;;|$$||%$$&&$%%%%%$&&&&@@@!.``.    ....`.
|!!!||!!|!!||!|||||||||||!!!!!!!;;;;;;;!!||||||||||!!!;;;;;;;;;|$$||$$$&&&$%%%|%$&&&@@@; .`.    .. ...
|!!!||!!||!!|!!|||||||||||!!!!!!!;;;;;!!||||||||!!!|||||!!;;;;;;|$$|!$$$&&&&$%%|%$&&&&@$' .`.   ..  ..
|!!!||!!||!!||!|||||||||||!!!!!!!;;;;;!||||||!!!|||||||||!::'::::!$$!!%$$&&&&$$%!!%$$&&&!. .`.  ..
|!!!|||!|||!!|!!|||||||||||!!!!!!!;;;!!||||!!|||||||||!;;!!!!!!;;;|$%!|$$$&&&&&$|`.;$$&&|`  .`...
|!!!!||!||||!!|!!||||||||||!!!!!!!!!;!|||!||||||||!!!!||!:'`.`:;!!!%$%!|$$$&&&&&$;  '%$&$;   ``
|!!!!||!!||||!!|!!|||||||%||!!!!!!!!!!||||||||||!!!|!:.      ....`';|||!|$$&&&&&@|`  '%&$%:   ..
|!!!!|||||||||!|||!||||||%%|!!|!!!!!!!||||||||!!!;` ...      ...';||%$|;!%$$&&&&@$:   :$&$$|.  ..
||!!!||||||||||!!||||||||%%||!!|!!!!!!|||||||!!'..```..``... `:;;;!|%$$|!|%$&&&&&&;   '|$%:!$: ...
||!;!|||||||||||!!%|||||%%%%|||||!|!!|||||||!'..```.`'```..`!%!!%%%%|$$||!|$$&&&&&;   ';!%: `|%`..
||!!!!!|||||%||||!!%%||%%%%%%|||||||!||||||;:`.``.`:;;`.':```:':|%%%%$$%|!;|&&&&&$:   ''`!;    :|:.
|||!!!!!||||%%%|%%||%%|%%%$$%|||%|!||!||||!:`....';;!|%;.```''::!%%%|%$$$|';$&&&&%'  .`  ::       .`''`. .``.
|||!!!!!||||%%%%%%%|||%%%$$$$%|%%%||%|!||!:```....`;|%$$|'':`'!;!%%%%%%$&@%!%&$$&!. .`.  ``.      .
|||!!!|!!|%%%%%%%%%%%||%%%$$$%|%%%%||%|!|!!|||||||!;::|$$$%|%%%!!|%%%%%%$&&&$$$$%' .`    ..
|||!!!||!!|%%%%%%%%%%%%||%%%$$%|%%$%|%%!!|||||||||||||||!!!||||%%%%%%%%%$$$$$$$$&%:.     ..
||||!!|%|!;!%%%%%%%%%%%%%%|%%%$||%$%%|%|!!||||||||||||||%%%%%%%%$$$%%%%$$$$%%$$$&&&&&&$%'..
!|||!!!|%|!;!%%%%%%%%%%%%%%%|%%%||%%%||%|!!!||||||||||||%%%%%%%%%%%%%%%$$$$%%$$$$$$$$$$%'
;!||!!!|%%%|!;|%%%%%%%%%%%%%%%%|%||%%%!!||!!!|%%||||||%%%%%%%%%%%%%%%%$$$$%%%%%$$$$$$$$!`
;;!||!!!|%%||!;!||%%%%%%%%%%%%%%%||%%%|!!|||!!!|%$%|||%%%%%%%%%%%%%%%%%%%%%%%$$$$$$$$$$;.
;;;||!!!!|%%||!;;!|%%%%%%%|||||%%|||||||!!||||||||%$%|%%%%%%%%%%%%%%%%$%%%%%$$$$$$$$$$%'
!!;!|!;;!!|%%|||!;!||%%%||||||||||||||||!!|%||||||||%%||%%%%%%%%%%%%$$$$$$$$$$$$$$$$$$!`
!!;;!!;;!!!||||||!;;!|||||||||||||||!||||!;;|%%%%%%%|%%%%%%%%%%%%%%%$$$$$$$$$$$$$$$$$$%'
!!!;;!!;;!!!||||||!!;;!||||||||||||||!||||!!!!%$%|%%%%%%%%%%%%%%%%%%$$$$$$$$$$$$$$$$$$$%'
!!!!;;!!;;;!!!|||||!!::;|||||!|||||||!!|||||!!!|$$%%%%%%%%%%%%%%%$$$$$$$$$$$$$$$$$$$$&&&$:
;;!!!!;!;;;;!!!|||||!!;::;!|!!!!||||||!!|||%%|!!!%&%%%%%%%%%%%%%%$$$$$$$$$$$$$$$$$$$$$&$!`
|!!!!;!;;;;::;!!!||!||!;;;;;!!!!!!|||||!!|||%%|||!|$&$%%%%%%%%$$$$$$$$$$$$$$$$$$$$$$$$%!`
:::;!;;;;::;::;;!!|||!!!!;;;;;!!!!!!||||!!|||%$%%||||$&$%%%%%%$$$$$$$$$$$$$$$$$$$$$$$$$%'
;;;;;!!!!!;:::;;:;!!||!!!!!;;;;;!!!!!!||||!!||%$%%%%%%%%$$%%%$$$$$$$$$$$$$$$$$$$$$$$$$$$$:
;;;;;;;;;!!!;::;;;:;!!|||||!!!!;;;;!!!!!|||||||%$$%%%%%%%%$$$$$$$$$$$$$$$$$$$$$$$$$$$$&$!.
;;;;;;;;:::::::::;;;;;;!||!!!!!!!!;;;!!!!!||||||||$$%%%%%%%%%%$$$$$$$$$$$$$$$$$$$$$$$$$&!.
;;;;;;;::;;:::;;;;:;;;;;;;;!!!|!!!!!!;;;!!!!!|%%||||%$%%%%%%%%%$$$$$$$$$$$$$$$$$$$$$$$$&%`
;;;;;;;:::;;::;;;;;;;;;;;;::;!!!!!!!!|!;!!!!!!!|%%%%%%%%%%$$$$$$$$$$$$$$$$$$$$$$$$$$$$$&&:
;;;;;;;::;::;:;;;;;;;;;!!!!!!!;;!!|||||!!!|!!!!!!!|%%%%%%%%%%%%%%%%$$$$$$$$$$$$$$$$$$$$&&|`
;;;;;;;::;;;::;;;;;;;;;;!!!!!!!!!||||||||;!!|||||||||%%%%%%%%%%%%%%%$$$$$$$$$$$$$$$$$$$$&&!.
;;;;;;;::;;;;::;;;;;;;;;;!!!!!!!!|||||||||;;;!!|||||||||%%%%%%%%%%%%%%%%$$$$$$$$$$$$$$$$$&|`
!;;;;;;;::;;;:;;;;;;;;;;;!!!!!!!!!|||||||%!;;;;;!||||||||||%%%%%%%%%%%%%%%$$$$$$$$$$$$$$$$!.
;!;;;;;;::;;;:;;;;::;;;;;!!!!!!!!!|||||||%%!;;;;;;!!!|||||||%%%%%%%%%%%%%%%%%%$$$$$$$$$$&|`
:;!!;;;;:::;;;:;;;:::;;;;;!!!!!!!!||||||||$|;;;;;;;;!!!!||||||||%%%%%%%%%%%%%%%%%%%$$$|'
::;!!;;;::::;;:;;;;::;;;;;;!!!!!!!!|||||||$$!;;;;;;;;;;;!!!!!||||||%%%%%%%%%%%%|!:`.
:::;!!;;;:::;;;;;;;:::;;;;;!!!!!!!!||%||||%&%!;;;;;;;;;;;;!!!!!!!!!!!|!;:`.
::::;!!!;::::;::;;;::::;;;;;!!!!!!!!|%%|||!%&%;;;;;;;;;;;;;;;;;;;;;%|`
:::::;!!!;:::::::;;:::::;;;;!!!!!!!!||%%%%!;%$|;;;;;;;;;;;;;;;;;;%@@$:
::::::;!!!:::::':;;::::::;;;;;!!|!!!||%$%%|!;%$!;;;;;;;;;;;;;;;;|$&@@|`
:::::':;;!;::::'';;;::::::;;;;!!!|!!!||%$%%|;;%%;;;;;;;;;;;;;;!||%$&#@|`
::::::':;;;:::''':;;:::::::;;;!!!||!!!|%$$%%|;;||;;;;;;;;;;;!||||%%%&#@%'
:::::::':;;;::'. ';;::::::::;;;!!!|!!!||%$$$%;;;||;;;;;;;;;|%%|||||%%&@@*/
#include <bits/stdc++.h>
using namespace std;

int n,k;
map<int,int> vals;
vector<int> ins;
const int jt=1000000007;

int ksmii(int a,int b){
	if(!b){
		return 1;
	}
	int x=ksmii(a,b>>1);
	x=1ll*x*x%jt;
	if(b&1){
		x=1ll*x*a%jt;
	}
	return x;
}

int dfs(int now){
	if(vals.count(now)){
		return vals[now];
	}
	int &val=vals[now];
	val=ksmii(k,(now+1)/2);
	for(int i=0;i<ins.size();i++){
		if(now%ins[i]==0&&ins[i]!=1){
			val=(val-dfs(now/ins[i])+jt)%jt;
		}
	}
	return val;
}

int main(){
	scanf("%d%d",&n,&k);
	for(int i=1;i*i<=n;i++){
		if(n%i==0){
			ins.push_back(i);
			if(i*i!=n){
				ins.push_back(n/i);
			}
		}
	}
	dfs(n);
	int ans=0;
	for(map<int,int>::iterator it=vals.begin();it!=vals.end();it++){
		int ff=it->first;
		if(ff%2){
			ans=(ans+1ll*ff*it->second)%jt;
		}else{
			ans=(ans+1ll*ff/2*it->second)%jt;
		}
	}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 256