小红的扔骰子
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

小红拿到了一个正整数p,初始p=1。小红每次扔一个三面骰(每次等概率随机扔出1或者2或者3),每次扔出来一个数字就会使得p乘上这个数字。
小红想知道,当p第一次是x的倍数时,需要扔的次数期望是多少?

输入描述:

一个正整数x
1\leq x\leq 10^{18}

输出描述:

如果永远无法使得p变成x的倍数,请输出-1。
否则输出一个整数,代表最终的期望模10^9+7的值。可以证明,这个期望一定是一个有理数,若写成p/q的形式,你需要找到一个x∈[1,1000000006]满足,x*q \equiv p(mod\ 1000000007)
示例1

输入

复制
2

输出

复制
3

说明

小红只要扔出一个2即可完成目标,最终的次数期望是:1*1/3+2*2/9+3*4/27+……,该无穷级数收敛于3。
示例2

输入

复制
5

输出

复制
-1