Background

On the black soil, a small sprout breaks through the ground.

Over several months, it drinks sweet rain and dew, enjoys warm sunlight, and becomes greener and greener.

It grows taller and stronger, as if it is going to reach through the clouds.

It grows into a big tree, longing to go into the sky and see this beautiful world.

Problem Description

Please note that this problem has unusual time and memory limits.

Given a number $x$, build a rooted tree using the following rules:

• The root node is $\lang 0, x \rang$.

• For a node $\lang i, j \rang$, if $j < 3$, then it is a leaf node. Otherwise, its children are, for any $1 \le k$ and the number of digits of $j$ is $\ge k$, $\lang j_k, k \rang$, where $j_k$ is the $k$-th digit of the ternary representation of $j$ from left to right.

Find the number of leaf nodes of this tree.

Input Format

One line with two integers $p, q$, meaning $x = p^q$.

Output Format

One line with one integer, which is the required answer.

The problem guarantees that the answer fits in the $\tt int64$ range.

9 1

4

27 1

6

Hint

This problem uses bundled SubTask testing.

For $100\%$ of the testdata, $p^q \le 3^{3^{35}}$ ($10^{10^9} \lt 3^{3^{35}} \lt 10^{2.5 \times 10^9}$), and it is guaranteed that $p = 3^l$ ($l \in \mathbb N^+$).

Translated by ChatGPT 5