팔찌

그는 여러 색의 구슬을 엮어 팔찌를 만드는 취미에 빠졌다. 그가 만드는 팔찌는 구슬 여러 개를 일렬로 놓고 실로 꿴 다음 실의 양 끝을 묶어 원형으로 만든 것이다. 만들 수 있는 팔찌는 무궁무진하지만, 비슷한 것을 싫어하는 그는 팔찌를 회전시키거나 뒤집어서 구슬 색의 순서가 같아지면 같은 종류로 취급하기로 했다.

위 그림은 빨간 구슬과 파란 구슬을 번갈아 엮어 구슬 네 개로 만든 팔찌다. 어떤 색을 기준으로 보느냐에 따라 두 가지로 보인다. 그러나 왼쪽 팔찌를 시계 방향으로 조금 회전시키면 오른쪽 팔찌와 구성이 같아지므로, 한 가지 종류로 세야 한다.

위 그림은 구슬 다섯 개로 만든 팔찌다. 왼쪽 팔찌를 좌우로 뒤집으면 오른쪽 팔찌가 되므로, 이 둘도 한 가지 종류로 세야 한다.

그가 가진 구슬 색은 $K$종류이고, 각 색의 구슬은 무한히 많이 준비되어 있다. 구슬을 $N$개 이하만 사용해서 만들 수 있는 서로 다른 팔찌의 종류 개수를 구하는 프로그램을 작성하라. 구슬을 하나도 사용하지 않은 팔찌도 한 종류로 센다.

첫 줄에 사용할 수 있는 구슬의 개수 $N$과 구슬 색의 종류 수 $K$가 공백으로 구분되어 주어진다. ($1 \le N \le 10^6$, $1 \le K \le 10^6$)

첫 줄에 구슬을 $N$개 이하만 사용해서 만들 수 있는 팔찌의 종류 개수를 출력한다. 이 수는 매우 커질 수 있으므로 1,000,000,007로 나눈 나머지를 출력한다.