P3757 [CQOI2017] Lao C's Keyboard

Lao C is a programmer. As an excellent programmer, Lao C owns a distinctive keyboard, which is said to greatly increase the speed of writing programs and, driven by some mysterious power, make the programs run very fast. Little Q is also a programmer. One day he sneaked into Lao C's home to see what was so special about the keyboard. He found that the keyboard has $n$ keys. Although these $n$ keys are neatly arranged in a single row, the height of each key is different. The clever Little Q immediately represented the height of each key with the integers $1 \sim n$, obtaining a permutation $h_1, h_2, \cdots , h_n$ of $1 \sim n$. In order to later build an imitation keyboard (the heights of its keys also form a permutation of $1 \sim n$), and also to avoid being exactly the same as Lao C's keyboard, Little Q decided to record several pairs of height relations between keys. As a programmer, Little Q of course did not just pick a few pairs at random, but chose them in a very regular way: for $i=2,3, \cdots ,n$, Little Q recorded a character '', indicating $h_{\frac i2}h_i$. Thus, Little Q obtained a string of length $n-1$ and happily went home. Now Little Q wants to know how many keyboards satisfy the height relations he recorded. Although Little Q does not want his keyboard to be completely identical to Lao C's, the completely identical one also counts as satisfying the requirement. The answer may be large; you only need to tell Little Q the result modulo $1,000,000,007$.

The input consists of a single line containing a positive integer $n$ and a string of length $n - 1$ consisting only of '', representing the number of keys on the keyboard and the information recorded by Little Q, separated by a space.

Output a single line containing an integer, the answer modulo $1,000,000,007$.

 Translated by ChatGPT 5