Вася учится в выпускном классе школы, и скоро ему надо сдать экзамены. В качестве подготовки он изучает многочлены. Многочлен — это функция P(x) = a₀ + a₁x¹ + a₂x² + ... + a_nxⁿ. Числа a_i называются коэффициентами многочлена а неотрицательное целое число n — степенью многочлена.

Вася — азартный мальчик. Он поспорил с друзьями, что решит любую задачу о многочленах. Друзья предложили ему следующую задачу: «Определить, сколько существует многочленов P(x) с целыми неотрицательными коэффициентами a_i, таких, что , а , где , a и b — данные целые положительные числа.»

Вася совсем не любит проигрывать споры, но по данной задаче у него совсем нет идей, поэтому он обратился к вам за помощью.