Иностранный торговец животными Карбофос успел найти покупателя похищенного полосатого слона. Он отправил ему в Германию шифрованное сообщение.

В тот же день братьям детективам доложили о пропаже из столичного музея шифровальной машины <<Энигма 43>>. Шеф уверен, что это не совпадение.

<<Энигма 43>> всегда генерирует целое число $\overline{a_1a_2\ldots a_n}$ ($0 \le a_i \le 9$, $a_1 \neq 0$) длины $n$, обладающее особым свойством: ни у каких двух соседних пар цифр не совпадает НОД (наибольший общий делитель). Другими словами, для любой тройки подряд идущих цифр $\overline{a_i a_{i+1} a_{i+2}}$ верно, что $\gcd(a_i, a_{i+1}) \neq \gcd(a_{i+1}, a_{i+2})$. Любое число, обладающее таким свойством, может быть сгенерировано. В этой задаче $\gcd(0, 0) = 0$.

В сообщении могут содержаться важные для следствия данные, но его проблематично восстановить. Коллега предложил воспользоваться полным перебором.

Помогите братьям Колобкам посчитать количество сообщений, которые Карбофос мог отправить с помощью <<Энигма 43>>. Так как ответ может быть большим, посчитайте его по модулю $10^9 + 7$.

\begin{center}
\includegraphics{pic5.png}
\end{center}
