#4333. JSOI2012 智者的考验

公元1371年，太祖下令在北极阁上大建庙宇，短短几年，鸡笼山上便建成了帝王庙、关公庙、真武庙、功臣庙、蒋王庙、都城隍庙、卞壶庙、忠烈庙、刘越王庙、曹武惠王庙共十座庙宇，统称为“十庙”。 

后来，为了方便人们来鸡笼山进香礼佛，太祖下令疏通了鸡笼山下已淤塞多年的潮沟。于是，便有了“进香河”。 

然而并不是所有人都可以来鸡笼山的，太祖在进香河上修建了一座石桥，中间悬挂了一块高Rx宽Ry的机关格图（如下图所示）。所有格子都是活动可翻转的，一面是白色，一面是黑色，这里我们用0表示白色，用1表示黑色。初始情况下，所有格子都是白色面朝前的。有Rx+Ry个机关按钮，对应Rx行和Ry列。一个按钮一旦触发，就会引发对应的一行或一列的格子同时翻转。 

同时，善于识天象的谋臣刘基给出了一种黑白状态，称之为“厄运星”。每一位过往前去鸡笼山的人都需要触发且只触发一个按钮，触发后，如果来访者呈“厄运星”形状，则不允许通过。 

每一天要来鸡笼山的人数N是事先就知道的，同时天朝神威浩荡，每一位来者一开始总是有很大概率触发编号为1的按钮，我们不妨用数列A1,A2,…,AN来表示，问题保证了初始时候的A数列全为1。同时在整个问题中，Ai满足1<=Ai<=Rx+Ry。太祖很关心那些不允许去鸡笼山的人数。于是他时不时就会询问关于“某一段时间内会有多少人不能通过“厄运星”的考验”。然而那些前来鸡笼山的文人墨客并不愿意如此单一的操作。来访者有可能会突然决定修改自己的触发按钮。更麻烦的情况，结伴而来的连续若干人会突然决定修改触发按钮并且都去触发同一个按钮。 

现在这麻烦的问题交给了你。 

后记： 

等到了乾隆时期，一位人称纪昀的才子来访此地，告诉了人们一套方法，从此再也没有人会不被允许通过了。久而久之，鸡笼山烟火依旧，然这机关格图的故事便渐渐失传了。直到今天才再一次被世人所了解。