Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 3008
Gold Coins

Time Limit: 2 Seconds      Memory Limit: 65536 KB

As a merchant, Bill likes gold coins very much. One day, when he was counting his gold coins again and again, a witch came into his house. The witch told him that she could change his n coins to n^m. Of course, Bill knew how quickly the number was growing if m was more than 1. So he felt very happy. However, there was a precondition that Bill should answer the witch a question before he gained the coins as to the witch. Bill could use t(1 ≤ t ≤ n) bags to store the n^m coins and the num of coins in every bag should be equal. The question mentioned above was that how many ways there were to store the coins. Bill was disappointed for he wasn't able to solve it, but he also didn't want to give up. So he needed your help, maybe you would share the gold coins after solving it.

Input

Every test case contains two numbers n(1 ≤ n ≤ 10^8) and m(1 ≤ m ≤ 10), process to the end of file.

Output

For every case, print the number of storing ways in a line.

Sample Input

6 2

Sample Output

5


Author: WANG, Tao
Source: ZOJ Monthly, July 2008
Submit    Status