提示：本题中的九连环不允许 环同时上或下，与传统九连环不同。
九连环是一种源于中国的传统智力游戏。如图所示，九个的圆环套在一把“剑”上，并且互相牵连。
在传统的九连环中，第 个环可以装上“剑”（记为 ）或拆下“剑”（记为 ），当且仅当第 个环在剑上，且再之前的环不在剑上；特别地，第 个环可以任意上下。
本题中我们将会讨论更一般的情形，虽然这种扩展九连环不一定可以在物理意义上造出。
题目描述
一个扩展九连环，可以看作两个 01 串——规则串 和状态串 ，满足 。其中 表示第 个环是装上的， 表示第 个环是拆下的。
在同一局游戏中是不变的，而 每步会变化一个位置上的值（从 0 变成 1 或从 1 变成 0）。九连环被拆下，当且仅当 全是 0；九连环被装上，当且仅当 全是 1。
扩展九连环规定， 可以变化，当且仅当 是 的一个后缀。可以看出，传统的九连环就是 为 00...01 的特殊情形。
给出一个 ，问从拆下状态到装上状态至少需要几步，答案对 取模。