BALTIC-WAY 2025 Problem 10

A positive integer with 9 digits is called nice if it contains each digit from 1 to 9. A number is called wonderful if it is nice and for each $k = 1, \ldots, 9$, it holds that the $k$-th digit in the number is equal to the position of $k$ in the number. For example, 847296315 is wonderful:

• the first digit is 8, which is the position of 1 in the number,
• the second digit is 4, which is the position of 2 in the number,
• the third digit is 7, which is the position of 3 in the number, and so on.

Show that the number of wonderful numbers is even.