Several months ago our team thought that it would be quite good if we knew language of TruCoders, creatures that founded the first civilization on the Earth. (How, you haven't heard about them yet?!) But because they were much more intellectual beings than humans, their language (maybe) consisted of very many words and we doubt that we will be able to remember all of them.

It is known that every NSU2 teammate can memorize at most 10¹⁰⁰⁰⁰⁰ words. For example, if TruCoders' language consists of 4000 words, one of them can learn 2000 words and every of two others will learn 1000 words. And so NSU2 will be able to read all of TruCoders' texts.

And now we want you to write a program that can determine whether the team can read all of TruCoders' texts or not.

TruCoders' language is based on English lowercase letters. Overall set of TruCoders' words can be described as a string expression, giving the set of words. All TruCoders' words are strings (possibly empty) of letters. So:

1. Letter 'a'..'z' means the set consisting of one word consisting of this letter.
2. Symbol '0' (zero) means an empty set of words.
3. (<expression>) means the same set of words as <expression>.
4. <symbol> is either a lowercase letter or '0' or an expression in parentheses — (<expression>).
5. <expression> is <concatenation> or <concatenation₁>|<concatenation₂>|…
|<concatenation_n> and it means union of sets of words from all <concatenation_i>.
6. <concatenation> is <closure> or <closure₁><closure₂>…<closure_n> and it means set of all words that are concatenations of a word from <closure₁>, a word from <closure₂> and so on.
7. <closure> is <symbol> or <symbol>* or <closure>* and it means (if there is '*') <symbol>⁰|<symbol>¹|…|<symbol>ⁿ|… (arbitrarily many times) where <symbol>ⁱ means <symbol><symbol>…<symbol> (i times) and <symbol>⁰ means the set consisting of one empty word. And if <closure> is <symbol> it means the same set of words as <symbol> of course.

For example, if language is described as "((a|b)(c|d))", it consists of four words: "ac", "bc", "ad" and "bd".

In the input there is one nonempty string with maximal length of 10000 describing TruCoders' language.

If our team will be able to remember all words of TruCoders' language write 'F'. In the other case write 'N'.