Description
Domo is a brilliant dog. This day, he is sitting on the table and waiting for you to take him for a walk.
To finish your job, please find out the total number of blocks you need to fill to get the perfect image you want.
Given an integer N and a string S, we can generate an image with a width and height that are both 2N as below:
(1) if S == "1", we will fill all the blocks.
(2) if S == "0", all the blocks will remain empty.
(3) if S == "2StlStrSblSbr", we will divide the image into 4 squares with a width and height that are both 2N-1, where Stl, Str, Sbl, and Sbr are strings that generate the image of corresponding squares. (Stl generates the image of the top-left square, Str generates the image of the top-right square, and so on).
For example, if N = 2 and S = "20100", the image will be:
There's another example, if N = 3 and S = "221010011", the image will be:
Please find out the total blocks you need to fill. Furthermore, if the given S is invalid (i.e. S cannot generate the corresponding image), please output "Domo".
Once you solved this problem, please take Domo for a walk before dinner time!
Input
The input contains an integer N and a string S, where S only contains characters '0', '1', and '2'.
(1 ≤ N ≤ 5, 1 ≤ length(S) ≤ 20)
Output
Output the number of blocks you need to fill, or "Domo" if S cannot generate an image.
Note that you don't need to print '\n' at the end of the output.