1, 1, 2, 4, 9, 20, 46, 107, 253, 604, 1463, 3573, 8812, 21901, 54837, 138145, 350068, 891529, 2281092, 5860471, 15113614, 39109461, 101521521, 264286160, 689820642, 1804890193, 4733051924, 12437565725, 32746931264, 86375236835, 228212881032, 603915863737, 1600500761487