E. Elementary Magical School of Words
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

In a distant kingdom called Alfabétia, wizards did not use common spells — they used magical words. Each word was formed by lowercase letters of the alphabet, and its power did not lie in the letters themselves, but in the way they repeated.

The wisest of the wizards, Archmagus MagePetrus, noticed something curious: two words could be equally powerful, even if they had different letters, as long as they had the same pattern of repetition.

For example:

  • The word "aba" had a pattern where the first and third letters were the same, and the second was different.
  • The word "cbc" had the same pattern!
  • Even the strange "zfz" was like that too!

MagePetrus called this letter symmetry. He decided that, for magical purposes, words with the same pattern of letter repetition were equivalent — it did not matter which letters were used, only how they repeated.

Intrigued by the possibilities, MagePetrus proposed a challenge to the young apprentices of Alfabétia:

Given a number $$$n$$$, how many different magical patterns (i.e., how many distinct classes of words by letter symmetry) can be formed with words of size $$$n$$$, using letters from "a-z"?

We consider two strings equal, by letter symmetry, if one can be obtained from the other through a permutation of its letters. Formally, let $$$s$$$ be the string formed by the concatenation of the characters $$$s_1, s_2, \dots, s_n$$$ in that order and $$$A = \{a, b, \dots, z\}$$$ the set of lowercase letters of the Latin alphabet. We say that $$$s$$$ is equal to a string $$$t$$$ by letter symmetry if and only if there exists an injective function $$$f : A \to A$$$ such that $$$t$$$ is the string formed by the concatenation of the characters $$$f(s_1), f(s_2), \dots, f(s_n)$$$. The function $$$f$$$ being injective means that, for all characters $$$x, y \in A$$$, if $$$x \neq y$$$, then $$$f(x) \neq f(y)$$$.

For example, the strings "aba", "cbc", and "zfz" are considered equivalent, as they all have the same structure of letter repetition, while the strings "aa" and "ab" are different.

Input

The input consists of a single integer $$$n$$$ ($$$1 \leq n \leq 10^{6}$$$), representing the size of the strings to be considered.

Output

The output should be a single integer, representing the number of different strings of size $$$n$$$ that can be formed, taking into account the symmetry of letter permutations. Since the answer can be enormous, find it modulo ($$$10^{9} + 7$$$).

Examples
Input
3
Output
5
Input
1
Output
1
Input
5
Output
52
Input
1000000
Output
281893449
Note

For $$$n=3$$$:

The strings "aaa", "aab", "aba", "abb", and "abc" are examples of the distinct strings that can be formed.