Two Records

問題文

正整数 $X$ が与えられる。

はじめ、空文字列 $S, T$ があり、 $X$ が正である間、次の操作を繰り返す。

• $X$ を $3$ で割った余りを $r$ とする。
• $S, T$ のどちらか一方を選び、選んだ文字列の末尾に $r$ を文字として追加する。
• $X$ を $\left\lfloor\dfrac{X}{3}\right\rfloor$ に置き換える。

この操作が行われる回数を $N$ とすると $S,T$ の選び方は $2^N$ 通りある。

このうち、すべての操作を終えたとき $S=T$ となる選び方の個数を求めよ。

制約

• 入力はすべて整数である。
• $1 \le X \le 10^{18}$

入力

入力は以下の形式で標準入力から与えられる。

出力

答えを出力せよ。

サンプル

サンプル 1

入力

324

出力

12

例えば、 $S, T, S, T, S, T$ の順に選ぶことで $S = T = "001"$ となる。