Sunt N scaune într-un rând. N oameni vin pe rând pentru a le ocupa respectând următoarele reguli:

1. Dacă există un scaun care are doua scaune adiacente libere, ocupă acel scaun.
2. Daca nu există un astfel de scaun dar există un scaun cu un singur scaun adiacent liber, ocupă acel scaun.
3. Altfel, ocupă unul din scaunele libere.

Fie T(N) numărul de posibilități ca N scaune să fie ocupate de N oameni respectând regulile date.
Următoarea figură ilustrează situația T(4)=8.

Se poate verifica că T(10) = 61632 si T(1 000) mod 100 000 007 e egal cu 47255094.

Află T(1 000 000) mod 100 000 007.