Source

This problem is adapted from Long Long OJ. All rights reserved.

Problem Description

There are $n$ languages and several teams. It is known that any two teams master different sets of languages, and any two teams share at least one common language. Please find the maximum number of teams possible. Output the answer modulo $127237991$.

Input Format

A positive integer $n$.

Output Format

A positive integer representing the maximum number of teams.

Samples

1

1

2

2

1000

43504463

Data Range

• For $30\%$ of the data, $1 \le n \le 30$.
• For $70\%$ of the data, $1 \le n \le 10^5$.
• For $100\%$ of the data, $1 \le n \le 10^{17}$.