题目描述

现在有 $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}$