背景

九连环是中国民间玩具,解九连环是中国传统智益游戏。

九连环是以金属丝制成9个圆环,将圆环套装在横板或各式框架上,并贯以环柄。

游玩时,按照一定的程序反复操作,可使9个圆环分别解开,或合而为一。

描述

传统的九连环是有序的9个环,一开始9个环都套在架子上,只有第一个环可以从架子上取下。

而想要上下自由移动第i(i>1)个环,就必须满足第i-1个环在架子上,且第i-1个环之前的所有环(如果有)都不在架子上。

想要将九个环全部取下来是一件十分费力的事,至少需要经过341步取下/套上的操作。

“古人造字以纪数,起于一,极于九,皆指事也。”

本题的九连环与传统九连环有所不同,九是虚数,泛指多,所以本题讨论的是n连环。

给定n连环的两个状态A和B,求从A状态转移到B状态的步数。(←这里是第六自然段)

这个步数可能很大,你只需要给出答案对p取模的值即可。

输入格式

第一行两个空格隔开的正整数n和p。

第二行一个长度为n的01串A,从左至右第i个数字表示第i个环,0表示不在架子上,1表示在架子上。

第三行一个长度为n的01串B,从左至右第i个数字表示第i个环,0表示不在架子上,1表示在架子上。

输出格式

一个整数,表示答案对p取模的值。

样例输入

3 233
001
000

样例输出

7

样例解释

套上环1,套上环2,取下环1,取下环3,套上环1,取下环2,取下环1,共计7步。

数据范围与约定

  • 对于30%的数据:n\le25
  • 对于60%的数据:n\le64
  • 对于100%的数据:n\le2333333,p<2^{31}

来源

原创 (某梗加强)