病毒编码

【题目描述】

对一种计算机病毒的加密编码方式是这样决定的。对于一个存储单元，有Flag域与Data域。Flag域由M+2位二进制数表示，设从左向右数第一位为X1，第二位为X2，剩余M位组成一个二进制整数C。Data域为N位二进制数。

对于输入的共N+M+2个二进制位的Flag与Data域，被攻击的电脑会给出一个长度为N的二进制校验序列Test，病毒程序可以花费1的单位时间对Flag,Data,Test任意一位进行修改，以达到伪装欺骗的目的。现要用最短的时间使得该存储单元通过对方的校验码。

校验公式：(Data[i],Test[i]均为从左向右数第i位表示的二进制数)

Test[i]=Data[(i+(X2*2-1)*C) mod N] xor X1 (0<=i<N)

当N次校验全部通过时该存储单元通过校验。

【输入格式】

第一行包含两个整数M,N

第二行为一个长度为N的01串描述Data域

第三行为一个长度为N的01串描述Test串

(Flag域在攻击对方之前全为0)

【输出格式】

输出一个整数，表示最短的伪装时间除以1005060097的余数

【样例输入】

4 8

11011011

10010000

【样例输出】

3

【提示】

数据范围和注释

对于30%的数据，1<=N<=1000，1<=M<=10。

对于100%的数据，1<=N<=100000，1<=M<=16。

样例解释：Flag=100110或110010 ,Data与Test不变

【来源】

在此键入。