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

В тот же день братьям детективам доложили о пропаже из столичного музея шифровальной машины «Энигма 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$$$.