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: mod = 10**9 + 7
  
  
  def main():
      n, k = map(int, input().split())
      if n % 2 == 0:
          ans = pow(k, n // 2, mod) * (n // 2)
          ans -= k * (n // 2 - 1)
      else:
          ans = pow(k, (n + 1) // 2, mod) * n
          ans -= k * (n - 1)
      print(ans)
  
  
  if __name__ == "__main__":
      main()
  
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"}]