BBP公式

题号：NC203025
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

用无穷级数计算无理数的近似值的方法叫做丢番图逼近，相信你大一的数分课上一定学过用于计算 $\pi$ 的莱布尼茨公式：

$\frac{1}{1}-\frac{1}{3}+\frac{1}{5}-\frac{1}{7}+\dots=\frac{\pi}{4}$

还有类似的华理士公式：

$\lim _{n \rightarrow+\infty}\left(\frac{(2 n) ! !}{(2 n-1) ! !}\right)^{2} \frac{1}{2 n+1}=\frac{\pi}{2}$

问题在于，这些无穷级数里几乎每一项都是无限小数，因此，如果你想计算Π的前n位小数的准确数字的话，就需要计算无穷级数前 $O(n)$ 项的前 $n$ 位，然后把它们加起来，总的时间复杂度是 $O(n^2)$

但是1995年三位数学家（名字首字母分别是BBP，这也是公式名称的由来）发现了一个特殊的公式：

$\pi=\sum_{k=0}^{\infty}\left[\frac{1}{16^{k}}\left(\frac{4}{8 k+1}-\frac{2}{8 k+4}-\frac{1}{8 k+5}-\frac{1}{8 k+6}\right)\right]$

这个公式的特殊之处在于 $\frac{1}{16^k}$ 那一项，这意味着，在 $16$ 进制下，每计算这个级数的一项，便能得到一位准确数字，计算 $\pi$ 的任意 $n$ 位数字，时间复杂度都是 $O(n)$

最近的研究中，发现了许多满足如下形式的无理数的级数展开，但是对于此类公式更深一层次的特性的探索，还未有重大突破。

$\alpha=\sum_{k=0}^{\infty}\left[\frac{1}{b^{k}} \frac{p(k)}{q(k)}\right]$

你的任务就简单的多了，给出一个整数 $n$ ，求出 $\pi$ 在 $16$ 进制下的小数点后第 $n$ 位。

一个十进制整数。

一位大写进制数。

示例1

复制

复制

保证