output_description: Print the number of the sequences a that can be obtained after the procedure,
  modulo 10^9+7.
  
  * * *
input_description: The input is given from Standard Input in the following format:
  
      
      
      N K
attempt: import sys
  
  
  def MI():
      return map(int, sys.stdin.readline().rstrip().split())
  
  
  N, K = MI()
  mod = 10**9 + 7
  
  
  def divisor(n):  # nの約数のリスト
      res = []
      for i in range(1, int(n**0.5) + 1):
          if n % i == 0:
              res.append(i)
              if i != n // i:
                  res.append(n // i)
      return res
  
  
  A = divisor(N)
  
  d = {}  # d[i] = iの約数のリスト(iはNの約数)
  for a in A:
      d[a] = divisor(a)
  
  prime = []  # Nの素因数のリスト
  for i in range(2, int(N**0.5) + 1):
      if N % i == 0:
          prime.append(i)
          while N % i == 0:
              N //= i
  if N != 1:
      prime.append(N)
  
  mu = {}  # mu[i] = μ(i) (iはNの約数)
  for a in A:
      b = a
      r = 1
      for p in prime:
          if b % p == 0:
              r *= -1
              if b // p % p == 0:
                  r = 0
                  break
      mu[a] = r
  
  
  ans = 0
  for a in A:
      for b in d[a]:
          if a % 2 == 0:
              ans += mu[a // b] * pow(K, (b + 1) // 2, mod) * (a // 2)
              ans %= mod
          else:
              ans += mu[a // b] * pow(K, (b + 1) // 2, mod) * a
  
  print(ans)
  
problem_description: Statement
  
  Takahashi and Aoki are going to together construct a sequence of integers.
  
  First, Takahashi will provide a sequence of integers a, satisfying all of the
  following conditions:
  
    * The length of a is N.
    * Each element in a is an integer between 1 and K, inclusive.
    * a is a _palindrome_ , that is, reversing the order of elements in a will result in the same sequence as the original.
  
  Then, Aoki will perform the following operation an arbitrary number of times:
  
    * Move the first element in a to the end of a.
  
  How many sequences a can be obtained after this procedure, modulo 10^9+7?
samples: [{"input": "4 2", "output": "6\n    \n\nThe following six sequences can be obtained:\n\n  * (1, 1, 1, 1)\n  * (1, 1, 2, 2)\n  * (1, 2, 2, 1)\n  * (2, 2, 1, 1)\n  * (2, 1, 1, 2)\n  * (2, 2, 2, 2)\n\n* * *"}, {"input": "1 10", "output": "10\n    \n\n* * *"}, {"input": "6 3", "output": "75\n    \n\n* * *"}, {"input": "1000000000 1000000000", "output": "875699961"}]