import Control.Monad
 
data Tree a
    = Nil
    | Branch a (Tree a) (Tree a)
    deriving (Show, Eq)
 
notEach :: Tree Bool -> [Tree Bool]
notEach x = go id x []
  where
    go :: (Tree Bool -> Tree Bool) -> Tree Bool -> [Tree Bool] -> [Tree Bool]
    go f Nil = id
    go f (Branch b l r) =
        (f (Branch (not b) l r) :) .
        go (f . \n -> Branch b n r) l .
        go (f . \n -> Branch b l n) r
 
procreateL :: Int -> Tree Bool
procreateL 0 = Nil
procreateL n = Branch (n `rem` 2 == 0) (procreateL (n - 1)) (procreateL (n `div` 2))
 
procreateR :: Int -> Tree Bool
procreateR 0 = Nil
procreateR n = Branch (n `rem` 2 == 0) (procreateR (n `div` 2)) (procreateR (n - 1))
 
test :: IO ()
test = do
    guard $ notEach (procreateL 3) == [Branch True (Branch True (Branch False Nil Nil) (Branch False Nil Nil)) (Branch False Nil Nil),Branch False (Branch False (Branch False Nil Nil) (Branch False Nil Nil)) (Branch False Nil Nil),Branch False (Branch True (Branch True Nil Nil) (Branch False Nil Nil)) (Branch False Nil Nil),Branch False (Branch True (Branch False Nil Nil) (Branch True Nil Nil)) (Branch False Nil Nil),Branch False (Branch True (Branch False Nil Nil) (Branch False Nil Nil)) (Branch True Nil Nil)]
    guard $ notEach (procreateR 3) == [Branch True (Branch False Nil Nil) (Branch True (Branch False Nil Nil) (Branch False Nil Nil)),Branch False (Branch True Nil Nil) (Branch True (Branch False Nil Nil) (Branch False Nil Nil)),Branch False (Branch False Nil Nil) (Branch False (Branch False Nil Nil) (Branch False Nil Nil)),Branch False (Branch False Nil Nil) (Branch True (Branch True Nil Nil) (Branch False Nil Nil)),Branch False (Branch False Nil Nil) (Branch True (Branch False Nil Nil) (Branch True Nil Nil))]
    guard $ length (notEach $ procreateL 150) == 1564307
    guard $ length (notEach $ procreateR 150) == 1564307
 
main = test

aW1wb3J0IENvbnRyb2wuTW9uYWQKCmRhdGEgVHJlZSBhCiAgICA9IE5pbAogICAgfCBCcmFuY2ggYSAoVHJlZSBhKSAoVHJlZSBhKQogICAgZGVyaXZpbmcgKFNob3csIEVxKQoKbm90RWFjaCA6OiBUcmVlIEJvb2wgLT4gW1RyZWUgQm9vbF0Kbm90RWFjaCB4ID0gZ28gaWQgeCBbXQogIHdoZXJlCiAgICBnbyA6OiAoVHJlZSBCb29sIC0+IFRyZWUgQm9vbCkgLT4gVHJlZSBCb29sIC0+IFtUcmVlIEJvb2xdIC0+IFtUcmVlIEJvb2xdCiAgICBnbyBmIE5pbCA9IGlkCiAgICBnbyBmIChCcmFuY2ggYiBsIHIpID0KICAgICAgICAoZiAoQnJhbmNoIChub3QgYikgbCByKSA6KSAuCiAgICAgICAgZ28gKGYgLiBcbiAtPiBCcmFuY2ggYiBuIHIpIGwgLgogICAgICAgIGdvIChmIC4gXG4gLT4gQnJhbmNoIGIgbCBuKSByCgpwcm9jcmVhdGVMIDo6IEludCAtPiBUcmVlIEJvb2wKcHJvY3JlYXRlTCAwID0gTmlsCnByb2NyZWF0ZUwgbiA9IEJyYW5jaCAobiBgcmVtYCAyID09IDApIChwcm9jcmVhdGVMIChuIC0gMSkpIChwcm9jcmVhdGVMIChuIGBkaXZgIDIpKQoKcHJvY3JlYXRlUiA6OiBJbnQgLT4gVHJlZSBCb29sCnByb2NyZWF0ZVIgMCA9IE5pbApwcm9jcmVhdGVSIG4gPSBCcmFuY2ggKG4gYHJlbWAgMiA9PSAwKSAocHJvY3JlYXRlUiAobiBgZGl2YCAyKSkgKHByb2NyZWF0ZVIgKG4gLSAxKSkKCnRlc3QgOjogSU8gKCkKdGVzdCA9IGRvCiAgICBndWFyZCAkIG5vdEVhY2ggKHByb2NyZWF0ZUwgMykgPT0gW0JyYW5jaCBUcnVlIChCcmFuY2ggVHJ1ZSAoQnJhbmNoIEZhbHNlIE5pbCBOaWwpIChCcmFuY2ggRmFsc2UgTmlsIE5pbCkpIChCcmFuY2ggRmFsc2UgTmlsIE5pbCksQnJhbmNoIEZhbHNlIChCcmFuY2ggRmFsc2UgKEJyYW5jaCBGYWxzZSBOaWwgTmlsKSAoQnJhbmNoIEZhbHNlIE5pbCBOaWwpKSAoQnJhbmNoIEZhbHNlIE5pbCBOaWwpLEJyYW5jaCBGYWxzZSAoQnJhbmNoIFRydWUgKEJyYW5jaCBUcnVlIE5pbCBOaWwpIChCcmFuY2ggRmFsc2UgTmlsIE5pbCkpIChCcmFuY2ggRmFsc2UgTmlsIE5pbCksQnJhbmNoIEZhbHNlIChCcmFuY2ggVHJ1ZSAoQnJhbmNoIEZhbHNlIE5pbCBOaWwpIChCcmFuY2ggVHJ1ZSBOaWwgTmlsKSkgKEJyYW5jaCBGYWxzZSBOaWwgTmlsKSxCcmFuY2ggRmFsc2UgKEJyYW5jaCBUcnVlIChCcmFuY2ggRmFsc2UgTmlsIE5pbCkgKEJyYW5jaCBGYWxzZSBOaWwgTmlsKSkgKEJyYW5jaCBUcnVlIE5pbCBOaWwpXQogICAgZ3VhcmQgJCBub3RFYWNoIChwcm9jcmVhdGVSIDMpID09IFtCcmFuY2ggVHJ1ZSAoQnJhbmNoIEZhbHNlIE5pbCBOaWwpIChCcmFuY2ggVHJ1ZSAoQnJhbmNoIEZhbHNlIE5pbCBOaWwpIChCcmFuY2ggRmFsc2UgTmlsIE5pbCkpLEJyYW5jaCBGYWxzZSAoQnJhbmNoIFRydWUgTmlsIE5pbCkgKEJyYW5jaCBUcnVlIChCcmFuY2ggRmFsc2UgTmlsIE5pbCkgKEJyYW5jaCBGYWxzZSBOaWwgTmlsKSksQnJhbmNoIEZhbHNlIChCcmFuY2ggRmFsc2UgTmlsIE5pbCkgKEJyYW5jaCBGYWxzZSAoQnJhbmNoIEZhbHNlIE5pbCBOaWwpIChCcmFuY2ggRmFsc2UgTmlsIE5pbCkpLEJyYW5jaCBGYWxzZSAoQnJhbmNoIEZhbHNlIE5pbCBOaWwpIChCcmFuY2ggVHJ1ZSAoQnJhbmNoIFRydWUgTmlsIE5pbCkgKEJyYW5jaCBGYWxzZSBOaWwgTmlsKSksQnJhbmNoIEZhbHNlIChCcmFuY2ggRmFsc2UgTmlsIE5pbCkgKEJyYW5jaCBUcnVlIChCcmFuY2ggRmFsc2UgTmlsIE5pbCkgKEJyYW5jaCBUcnVlIE5pbCBOaWwpKV0KICAgIGd1YXJkICQgbGVuZ3RoIChub3RFYWNoICQgcHJvY3JlYXRlTCAxNTApID09IDE1NjQzMDcKICAgIGd1YXJkICQgbGVuZ3RoIChub3RFYWNoICQgcHJvY3JlYXRlUiAxNTApID09IDE1NjQzMDcKICAgIAptYWluID0gdGVzdA==