困难数学题

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

题目描述

求 $\left ( \sum_{i=1}^{n} f(i) \right )\bmod 4\,294\,967\,296$ 。
定义 $f(i)$ 如下：
$v = (((114\,514^i \bmod 998\,244\,353) \times (1\,919\,810^i \bmod 1\,000\,000\,007)) \bmod 4\,294\,967\,296)\oplus 1\,777\,777\,777$
$w = (v + 2\,333\,333\,333) \bmod 4\,294\,967\,296$
$x = ((w \oplus (w >> 15)) \times 1\,145\,141\,145) \bmod 4\,294\,967\,296$
$y = ((x \oplus (x >> 14)) \times 1\,919\,810\,191) \bmod 4\,294\,967\,296$
$z = y \oplus (y >> 16)$
$f(i) = z$

$>>$ 表示右移运算， $\oplus$ 表示按位异或运算，详见OI-Wiki-位运算

输入描述:

输入一个正整数 。

输出描述:

输出一个整数表示答案。

示例1

输入

复制

输出

复制

1276898962

示例2

输入

复制

输出

复制

3922069770

示例3

输入

复制

输出

复制

3982808967