P2155 [SDOI2008] 沙拉公主的困惑

大富翁国因为通货膨胀，以及假钞泛滥，政府决定推出一项新的政策：现有钞票编号范围为 $1$ 到 $N$ 的阶乘，但是，政府只发行编号与 $M!$ 互质的钞票。房地产第一大户沙拉公主决定预测一下大富翁国现在所有真钞票的数量。现在，请你帮助沙拉公主解决这个问题，由于数量可能非常大，你只需计算出答案对 $R$ 取模后的结果即可。

无

无

对于 $100\% $ 的数据，$1\leq M\leq N\leq 10^7$，$1\leq T\leq 10^4$，$2\leq R\leq 10^9+10$ 且 $R$ 为质数。