Keyboard Permutation Inequalities

Old C is a programmer who owns a very unique keyboard. The keyboard has n keys arranged in a row and each key has a unique height forming a permutation of \(\{1,2,\dots,n\}\). One day, Little Q sneaks into Old C’s house and records a series of height relations between certain keys. For each key with index \(i\) (where \(i=2,3,\dots,n\)), he records a character which is either \( \), representing the relation between the height of the key at position \(\lfloor i/2 \rfloor\) and the height of the key at position \(i\):

[ \text{if } c_{i-1} = \text{( < )} \text{ then } h_{\lfloor i/2 \rfloor} < h_i, \quad \text{if } c_{i-1} = \text{(>)} \text{ then } h_{\lfloor i/2 \rfloor} > h_i. ]

Your task is to determine how many permutations \(h_1, h_2, \dots, h_n\) satisfy all of these relations. Print the count modulo \(10^9+7\). Note that even if Little Q’s record exactly matches Old C’s keyboard, it is considered a valid configuration.

inputFormat

The input consists of a single line containing a string of length \(n-1\) composed of the characters ''. Here, \(n\) is implicitly defined as the length of the string plus one.

outputFormat

Output a single integer, which is the number of valid permutations satisfying the given conditions, taken modulo \(10^9+7\).

sample

<

1