该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

背景

We are living in a world of goldfish.
神探夏洛克连载题目之第二章：致命游戏（Third Question）。（题目顺序不按照时间顺序进行）

描述

粉红色的手机里传来了一个小孩的声音：“给你一个完全图，求它的生成树个数？1秒钟内回答问题。”

Sherlock：他们居然绑架小孩？！

这个问题对于夏洛克来说当然很简单，可是作为他的计算姬大脑，你需要马上回答出答案。

格式

输入格式

第一行包含两个数，表示完全图顶点个数n(1<=n<=10^16)，以及模的值mod(1<=mod<=10^16)。

输出格式

第一行包含一个数，表示答案%mod。

样例1

样例输入1

4 5

样例输出1

1

后记

你成功的解决了这个问题，可是游戏并没有结束，疯狂的Moriaty还会继续给出什么题呢？。

来源

Bill_Yang原创神探夏洛克系列2.3