版权声明

本题版权归 Long Long OJ 所有。

题目描述

现在有 $n$ 种语言和若干支队伍，已知任意两个队伍掌握的语言互不相同，并且任意两个队伍之间至少有一种共同的语言。请你求出队伍数量的最大值。答案对 $127237991$ 取模。

输入格式

一个正整数 $n$。

输出格式

一个正整数，代表最大队伍数量。

样例

1

1

2

2

1000

43504463

提示

• 对于 $30\%$ 的数据，$1 \leq n \leq 30$。
• 对于 $70\%$ 的数据，$1 \leq n \leq 10^5$。
• 对于 $100\%$ 的数据，$1 \leq n \leq 10^{17}$。