Description

请留意本题并不寻常的时空限制。

给定一个数 $x$，用如下规则建立一棵有根树：

• 根节点为 $\lang0,x\rang$。

• 对于一个节点 $\lang i,j\rang$，若 $j < 3$，则它是叶子节点，否则它的子节点为对于任意 $1 \le k$ 且 $j$ 的位数 $\ge k$， $\lang j_k, k\rang$，其中 $j_k$ 为它三进制表示从左向右的第 $k$ 位。

求这棵树的叶子节点的数目。

Input Format

一行两个整数 $p, q$，表示 $x = p^q$。

Output Format

一行一个整数，即为所求。

题目保证答案在 $\tt int64$ 范围内。

9 1

4

27 1

6

Hint

本题采用 SubTask 捆绑测试。

对于 $100\%$ 的数据，$p^q \le 3^{3^{35}}$（$10^{10^9} \lt 3^{3^{35} } \lt 10^{2.5 \times 10^9}$），保证 $p = 3^l(l\in \mathbb N^+)$。