program rotated_palindromes
  implicit none
  integer(8), parameter :: md = 1000000007_8
  integer :: n, i, j, d(1500) = 0, m = 0
  integer(8) :: k, num(1500) = 0_8, ans = 0_8
  read(*,*) n, k
  i = 1
  do while (i*i <= n)
    if (mod(n,i) == 0) then
      m = m+1
      d(m) = i
      if (i*i == n) exit
      m = m+1
      d(m) = n/i
    end if
    i = i+1
  end do
  call quick_sort(d(1:m))
  do i = 1, m
    num(i) = pow(k,(d(i)+1)/2)
    do j = 1, i-1
      if (mod(d(i),d(j)) == 0) num(i) = modulo(num(i)-num(j),md)
    end do
  end do
  do i = 1, m
    ans = mod(ans+num(i)*int(d(i)/(2-mod(d(i),2)),8),md)
  end do
  write(*,'(i0)') ans
contains
  function pow(a,b) result(r)
    integer(8), intent(in) :: a
    integer, intent(in) :: b
    integer :: k
    integer(8) :: r, p
    r = 1_8
    p = a
    k = b
    do while (k > 0)
      if (btest(k,0)) r = mod(r*p,md)
      p = mod(p*p,md)
      k = rshift(k,1)
    end do
  end
  recursive subroutine quick_sort(a)
    integer, intent(inout) :: a(:)
    integer :: n, l, r, m
    integer :: p
    n = size(a)
    l = 1
    r = n
    m = (n+1)/2
    p = a(l)+a(m)+a(r)-max(a(l),a(m),a(r))-min(a(l),a(m),a(r))
    do
      do while (a(l) < p)
        l = l+1
      end do
      do while (a(r) > p)
        r = r-1
      end do
      if (l >= r) exit
      a(l) = xor(a(l),a(r))
      a(r) = xor(a(l),a(r))
      a(l) = xor(a(l),a(r))
      l = l+1
      r = r-1
    end do
    if (l-1 > 1) call quick_sort(a(1:l-1))
    if (n > r+1) call quick_sort(a(r+1:n))
  end
end program rotated_palindromes