Экспоненциальные башни
Число 729 может быть записано в виде степени несколькими способами: 3^6, 9^3 и 27^2. Конечно, его можно записать как 729^1, но это не считается степенью. Мы хотим пойти еще дальше. Для удобства бдем использовать ^ для возведения в степень, поэтому определим a^b = a^b. Тогда число 256 можно также записать как 2^2^3 или 4^2^2. Напомним, что ^ является правоассоциативным, поэтому 2^2^3 означает 2^(2^3).
Определим башню степеней высоты k как выражение вида a[1]^a[2]^a[3]^.. ^a[k], где k > 1, целые числа a[i] > 1.
По заданной башне степеней высоты 3, представляющую некоторое целое число n, определите количество башен степеней высоты не более 3, которые представляют n.
Входные данные
Состоит из нескольких тестов, каждый содержится в отдельной строке. Каждый тест имеет формат a^b^c, где a, b и c - целые числа, 1 < a, b, c ≤ 9585.
Выходные данные
Для каждого теста выведите количество способов, которыми может быть представлено число n = a^b^c в виде башни из степеней высоты не более трех.
Магическое число 9585 выбрано так, чтобы результат всегда был меньше 2^63.