403162: GYM101055 E Nefertiti, the Queen of Egypt

Nefertiti was queen of Egypt, wife to Akhenaton, and is considered one of the most beautiful women in the history of the world. Her statue, which can be seen in the Altes Museum in Berlin, Germany, proves her rare beauty. The sculptor didn't even finish the work, leaving the iris of the left eyeball undone, to avoid the God's wrath.

The life of the queen of Egypt was very busy, and she had to take care of many things, including the court's food menu. Akhenaton was known for hating that the food repeated often, and even in regular intervals. He wished the dishes were not only different, but also that is would be almost impossible to discover when a dish would be repeated. This created a huge problem for the court's chefs, that had to create new dishes as well as plan the order they would be served.

Nerfertiti had, then, an idea. She made a list of N dishes that would be repeated. One request of her was that the difference between the dish served in the ith day and i was at most K. Such demand, as well as being for religious reasons, was also due to the fact that the ingredients for the dish i were acquired during this interval, and could not wait so much or they would rot.

Your task is, for each integer N (the number of different dishes) and an integer K, count the number of different arrangements of the dishes are valid. Notice that each arrangement can be modeled as a permutation p of {1, 2, ..., N}, and an arrangement is valid if |p(i) - i| ≤ K, for all i from 1 to N.

The input has a single integer K.

Limits

• 0 ≤ K ≤ 6

You should print 200 lines, in the ith line print the number of arrangements of size N = i that are valid. Print these numbers modulo 10⁹ + 7.

3

1
2
6
24
78
230
675
2069
6404
19708

The sample output only shows the first 10 lines of output.