UOJ Logo

NOI.AC

#48. fac

统计

题目描述

小 S 最近学到了“阶乘”的概念,想要考一考来参加 NOIP 的你。他知道你可能不清楚这是用来做什么的,所以他十分良心地告诉了你什么叫阶乘:

  • 只有非负整数能够计算阶乘。
  • 0 的阶乘是 1。
  • 对于正整数 $x$,我们通过连乘 $x(x-1)(x-2)\cdots$ 的方式计算 $x$ 的阶乘,直到被乘的一项为 0 则停止这个过程。
  • 例如,6 的阶乘为 $6 \times 5 \times 4 \times 3 \times 2 \times 1 = 720$。

那么,请看好他要问你的问题:

输入正整数 $a$ 与 $b$,请你计算 $a$ 的阶乘,除以 $b$ 所得的余数

输入格式

从标准输入读入数据。

输入共两行,第一行输入 $a$,第二行输入 $b$。

输出格式

输出到标准输出。

输出共一行,仅包含一个数,即所求的答案。

样例

输入

6
99

输出

27

解释

6 的阶乘为 720,除以 99 后所得的余数为 27。

各测试点数据规模与约定

对于 80% 的数据,保证 $a \leq 10,000,000$。

对于所有数据,保证 $a \leq 10^{100,000}, b \leq 10,000,000$。