〈 TREEのOI 2022 Spring 〉Counting By Ternary

题目背景

黑土地上,一棵小苗破土而出。 几个月里,它吮吸着甘甜的雨露,享受着温暖的阳光,愈发翠绿了起来。 ![](https://cdn.pixabay.com/photo/2019/03/05/12/52/plant-4036131_960_720.jpg) 它越长越高,越长越壮,似乎要突破云霄。 它长成了一棵大树,渴望着去天空中,看一看这美丽的世界。 ![](https://cdn.pixabay.com/photo/2015/02/24/15/41/wolf-647528_960_720.jpg)

题目描述

**请留意本题并不寻常的时空限制。** 给定一个数 $x$,用如下规则建立一棵有根树: - 根节点为 $\lang0,x\rang$。 - 对于一个节点 $\lang i,j\rang$,若 $j < 3$,则它是叶子节点,否则它的子节点为对于任意 $1 \le k$ 且 $j$ 的位数 $\ge k$, $\lang j_k, k\rang$,其中 $j_k$ 为它三进制表示从左向右的第 $k$ 位。 求这棵树的叶子节点的数目。

输入输出格式

输入格式


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

输出格式


一行一个整数,即为所求。 题目保证答案在 $\tt int64$ 范围内。

输入输出样例

输入样例 #1

9 1

输出样例 #1

4

输入样例 #2

27 1

输出样例 #2

6

说明

**本题采用 SubTask 捆绑测试。** | SubTask 编号 | 分值 | 特殊性质 | | :-----------: | :-----------: | :-----------: | | $0$ | $10$ | $p\le 3^{15}$,$q=1$ | | $1$ | $10$ | $p\le 3^{35}$,$q=1$ | | $2$ | $20$ | $p=3$,$q\le 3^{15}$ | | $3$ | $60$ | $p=3$,$q\le 3^{35}$ | 对于 $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^+)$。