U534160 进入 k 进制星球（T3）

$\ \ \ \ \ \ $在宇宙中有许许多多有文明的星球，但是不同文明使用的进制不同。LHRG李 是一位星际探险员，当他想进入某个星球时，需要先获得进入星球的密码。

$\ \ \ \ \ \ $宇宙联盟规定，对于一个进制为 $k$ 的星球，若你是本天第 $n$ 位进入该星球的生物，那么你的密码就为**在 $k$ 进制下 $n!!$ 的位数**。 $\ \ \ \ \ \ $由于每颗星球一般都有两个入口且同时允许生物进入，而 LHRG李 一般都喜欢在同一侧进入所有星球，导致了他的 $n$ 始终为偶数。 $\ \ \ \ \ \ $现在，LHRG李 知道了 $k$ 和 $n$ ，但是由于他被一个人传染得比较懒（你们应该都知道是谁的），懒得自己算了，所以请你帮他计算一下他进入这个星球的密码，让他顺利完成探险。

两个整数 $n$ 和 $k$。

一个整数，表示密码，计算方法见题目描述。

数据范围： | 子任务 | 测试点编号 | 总分数 | 数据范围 | | :----: | :----: | :----: | :----: | | **Subtask #1** | $1-10$ | 50 | $1\leqslant n \leqslant 2\times10^6$ | | **Subtask #2** | $11-20$ | 50 | $1\leqslant n \leqslant 2\times10^9$ | 对于 $100\%$ 的数据，$1\leqslant n \leqslant 2\times10^9$，$10 \leqslant k \leqslant 100$ 提示： > 1、双阶乘：双阶乘是一个数学概念，用 $n!!$ 表示。正整数的双阶乘表示不超过这个正整数且与它有相同奇偶性的所有正整数乘积。例如前 $6$ 个正整数的双阶乘分别为：$1!!=1$，$2!!=2$，$3!!=3$，$4!!=8$，$5!!=15$ 和$6!!=48$。 > 2、斯特林公式：斯特林公式（Stirling's approximation）是一条用来取 $n$ 的阶乘的近似值的数学公式。一般来说，阶乘的计算复杂度为线性。当要为某些极大的 $n$ 求阶乘时，常见的方法复杂度不可接受。斯特林公式能够将求解阶乘的复杂度降低到对数级。但是由于这个公式是一个近似公式，在 $n$ 非常小的时候求的值会产生偏差，但是当 $n$ 位于 $10^6$ 的数量级时，这个偏差已经非常之小。 $\qquad\!\!$公式内容：$n!\approx \sqrt{2\pi n} \left( \dfrac{n} {e} \right)^n$ > 3、$e$：自然常数，是自然对数的底数，数学中一个重要的超越数，是一个无限不循环小数。它的值约为 $2.718281828459$。 ------------- 出题者：LHRG李 [题解](http://lhrg.github.io/题解-U534160-【进入-k-进制星球】/)