# Lin the Racoon's Debut

Author: mathforces
Problem has been solved: 12 times

Русский язык | English Language

Lin the Racoon compiled a sequence of $100$ digits in which exactly $50$ digits $0$ and $50$ digits $1$. At the same time, for any positive integer $k$ from $1$ to $100$, among the first $k$ digits of Lin the Racoon's sequence, the digit $0$ does not occur more often than the digit $1$. And also for any $i = 44, 45, ..., 57$, if the $i$ -th digit of its sequence is $1$, then the $i + 1$ -th digit of this sequence is also $1$. Let $x$ be number of possible sequences that Lin the Racoon could make up. Find the reminder when $x$ is divided by $10^7$.