ACM International Collegiate Programming Contest 1989
Northwestern European Regionals

Problem C

 Filling the Gaps 

At the largest conference on coding and cryptography the following theorem needed a proof or a counterexample: Suppose you are given a set of binary strings of equal length -- thus each consists of 0's, 1's and/or *'s. Furthermore suppose the pattern of *'s is different for all words in the set. By this we mean: if you replace all 0's and 1's by any single character, say $, you obtain a set of distinct strings.

The claim is: if you replace the *'s by 0's and 1's in all possible ways, then you obtain a set that is at least as big as the set you started with.


{ 10*, *0*, *00 } produces { 100, 101, 000, 001 }

{ 100, 101, 10* } produces { 100, 101 }

Notice that the set in the latter example does not satisfy the condidtion mentioned above, so it does not provide a counterexample.

You program is to help experimentally test this claim (not prove it). As such, it needs to do two things:

  1. Determine whether the pattern of *'s is different for all words in the set (we use "words" and "binary strings" interchangeably), and
  2. Compute the number of words obtained by replacing the *'s by 0's and 1's.
The words will not be longer than 15 symbols.
There will not be more than 100 lines (word sets) in the file.


The input is a text-file that presents a sequence of sets. Each set is a single line of input and consists of its words delimited by spaces.


The output is a textfile that contains one line for each set, i.e., one output line for each input line. If the pattern of *'s is different for all the words in this set this line should contain YES (in uppercase), followed by a space and the number of distinct words obtained by expanding all of the *'s. Otherwise it should contain NO (in uppercase) only, with no following integer.

Sample Input

10* *0* *00
10** *011 *0*0
1100 1101 110* 10** *10*

Sample Output