B. Brilliant Idea
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

One day, a brilliant idea came to Colin's mind.

Consider a string $$$S$$$ of length $$$n$$$, indexed from $$$0$$$ to $$$n-1$$$, that consists of lowercase English letters. A successful turn consists of the following operations:

  • Choose two integers $$$l$$$ and $$$r$$$ such that $$$0 \le l \lt r \lt n$$$ and the substring $$$S_lS_{l+1}\ldots S_r$$$ contains at least two distinct characters.
  • Choose an index $$$p$$$ with $$$l \le p \le r$$$, and replace every character $$$S_i$$$ for $$$l \le i \le r$$$ with the character $$$S_p$$$.

For example, if $$$S=\texttt{abc}$$$ and Colin chooses $$$l=1$$$, $$$r=2$$$, and $$$p=2$$$, then $$$S$$$ becomes $$$\texttt{acc}$$$.

The process ends when no successful turn is possible. Let $$$ans_S$$$ be the maximum number of successful turns that can be performed starting from $$$S$$$. If Colin can perform successful turns indefinitely, then $$$ans_S$$$ is infinite.

Among all strings of length $$$n$$$ consisting of lowercase English letters, count:

  1. the strings for which $$$ans_S=0$$$;
  2. the strings for which $$$ans_S \gt 0$$$ and $$$ans_S$$$ is finite;
  3. the strings for which $$$ans_S$$$ is infinite.
Input

The only line contains a single integer $$$n$$$ ($$$2 \le n \le 10^9$$$), the length of the strings.

Output

Output three integers: the numbers of strings in the three categories above, in the same order. Output each number modulo $$$10^9+7$$$.

Example
Input
2
Output
26 650 0
Note

There are $$$26$$$ strings of length $$$2$$$ with $$$S_0=S_1$$$, and each of them has $$$ans_S=0$$$.

Each of the remaining $$$26 \cdot 25=650$$$ strings has two distinct characters. Exactly one successful turn can be performed, so each of them has $$$ans_S=1$$$.