Welcome to ZOJ
Information
Problems
Runs
Statistics
Ranklist
Clarification
68 - ZOJ Monthly, July 2008 - 1004
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


Submit    Status