$\hspace{15pt}$小F同学捡到了一个四面骰（即可以等概率扔出 $1,2,3,4$ 数字的骰子），请你求出扔该骰子刚好 $N$ 次时，扔过的骰子点数之积刚好是 $D$ 的倍数的概率.

$\hspace{15pt}$为了让输出总是整数！结果乘以 $100000$ 后向下取整数.

$\hspace{15pt}$每次运行只有一个样例.

Constraints

• $1 \leq N \leq 1000$
• $1 \leq D \leq 10^{18}$

Input

$\hspace{15pt}$通过标准输入输入数据，满足以下格式：

$N \ \ D$

Output

$\hspace{15pt}$输出一个数字，表示答案.

Samples

3 7

0

32 92876046336

10098