Time Limit: Java: 2000 ms / Others: 2000 ms
Memory Limit: Java: 65536 KB / Others: 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.
Every test case contains two numbers n(1 ≤ n ≤ 10^8) and m(1 ≤ m ≤ 10), process to the end of file.