#M060. 阶乘 mod 大质数

    ID: 5689 传统题 3000ms 512MiB 尝试: 1 已通过: 1 难度: 9 上传者: 标签>CF2700省选/NOI-根号分块连续点值插值卷积转化NTT倍增批量求逆阶乘逆元预处理滑动窗口快速乘防溢出难度分类

阶乘 mod 大质数

题目描述

这是一道模板题。

询问 n!n! 对 10003918356491000391835649 取模的结果。

1000391835649=226×3×4969+11000391835649 = 2^{26} \times 3 \times 4969+1,是一个 101210^{12} 级别的大质数,最小原根为 77。

输入格式

TT 组数据。

每组数据一个正整数表示 nn。

输出格式

TT 行,一行一个整数表示答案。

1
5
120

数据范围与提示

100%100\% 的数据保证 1≤T≤50,1≤n<10003918356491 \leq T \leq 50,1 \leq n < 1000391835649。