Pikachu

Pikachu is a well-known character in the Pokemon anime series. Pikachu can speak, but only 3 syllables: "pi", "ka", and "chu". Therefore Pikachu can only pronounce strings that can be created as a concatenation of one or more syllables he can pronounce. For example, he can pronounce the words "pikapi" and "pikachu".


We need to teach our Pikachu to use N different words, conveniently numbered 0 through N-1. To do this, we need to encode the words into N distinct strings Pikachu will be able to pronounce. For example, we may encode "electric" as "pikapi" and "mouse" as "pikachu". As Pikachu sometimes omits pauses between the words he says, the encoding we will use must be prefix-free. More formally, we need to choose strings code[0], code[1], ..., code[N-1] such that:

1. For any i, code[i] must be a string that is generated by concatenating one or more copies of the strings "pi", "ka" and "chu".
2. For any distinct i and j, code[i] is not a prefix of code[j].

Of course, there are infinitely many such codes. We want you to find all the most efficient codes. The N words we need to encode may have distinct frequencies. You are given the relative frequences of all words as a int[] freq. (I.e., the actual frequency of the i-th word is freq[i]/S, where S is the sum of all elements of freq.) For a given code, its total cost can be computed as the sum of (freq[i]*length(code[i])) over all i.


Let A be the minimal total cost that can be achieved, and let B be the number of distinct codes that have the total cost equal to A. Your method must return a int[] with two elements: element 0 should be the value A, and element 1 should be the value (B modulo 1,000,000,009).