TUYMAADA 2020 J8

In a horizontal strip $1 \times n$ made of $n$ unit squares the vertices of all squares are marked. The strip is partitioned into parts by segments connecting marked points and not lying on the sides of the strip. The segments can not have common inner points; the upper end of each segment must be either above the lower end or further to the right. Prove that the number of all partitions is divisible by $2^n$ . (The partition where no segments are drawn, is counted too.)

(E. Robeva, M. Sun)