import qualified Data.Map.Strict as Map
--import qualified Data.Map as Map
 
f (r, s, i0) | s==0                 = Left 1
             | s<0 || s>r*9 || r==0 = Left 0
             | otherwise            = Right (zip3 (repeat $ r-1) (map (s-) [i0..9]) (repeat 0), sum)
 
task :: Integer -> Integer -> Integer
task r k = evaluate f (r,k,1)
 
evaluate f n  = snd . go n $ Map.empty where
    go i m = case f i of
        Left  v      -> (m, v)
        Right (l, t) -> (Map.insert i r m', r) where
            (m', r) = fmap t $ foldr gf (m, []) l
            gf i (m, l) = fmap (:l) $ case Map.lookup i m of
                Just v  -> (m, v)
                Nothing -> go i m
main = do
    print $ task 200 $ 90

aW1wb3J0IHF1YWxpZmllZCBEYXRhLk1hcC5TdHJpY3QgYXMgTWFwCi0taW1wb3J0IHF1YWxpZmllZCBEYXRhLk1hcCBhcyBNYXAKCmYgKHIsIHMsIGkwKSB8IHM9PTAgICAgICAgICAgICAgICAgID0gTGVmdCAxCiAgICAgICAgICAgICB8IHM8MCB8fCBzPnIqOSB8fCByPT0wID0gTGVmdCAwCiAgICAgICAgICAgICB8IG90aGVyd2lzZSAgICAgICAgICAgID0gUmlnaHQgKHppcDMgKHJlcGVhdCAkIHItMSkgKG1hcCAocy0pIFtpMC4uOV0pIChyZXBlYXQgMCksIHN1bSkKCnRhc2sgOjogSW50ZWdlciAtPiBJbnRlZ2VyIC0+IEludGVnZXIKdGFzayByIGsgPSBldmFsdWF0ZSBmIChyLGssMSkKCmV2YWx1YXRlIGYgbiAgPSBzbmQgLiBnbyBuICQgTWFwLmVtcHR5IHdoZXJlCiAgICBnbyBpIG0gPSBjYXNlIGYgaSBvZgogICAgICAgIExlZnQgIHYgICAgICAtPiAobSwgdikKICAgICAgICBSaWdodCAobCwgdCkgLT4gKE1hcC5pbnNlcnQgaSByIG0nLCByKSB3aGVyZQogICAgICAgICAgICAobScsIHIpID0gZm1hcCB0ICQgZm9sZHIgZ2YgKG0sIFtdKSBsCiAgICAgICAgICAgIGdmIGkgKG0sIGwpID0gZm1hcCAoOmwpICQgY2FzZSBNYXAubG9va3VwIGkgbSBvZgogICAgICAgICAgICAgICAgSnVzdCB2ICAtPiAobSwgdikKICAgICAgICAgICAgICAgIE5vdGhpbmcgLT4gZ28gaSBtCm1haW4gPSBkbwogICAgcHJpbnQgJCB0YXNrIDIwMCAkIDkw