{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e约翰农场主购买了一块郁郁葱葱的矩形牧场,由\u003ci\u003eM\u003c/i\u003e乘以\u003ci\u003eN\u003c/i\u003e(1 ≤ \u003ci\u003eM\u003c/i\u003e ≤ 12; 1 ≤ \u003ci\u003eN\u003c/i\u003e ≤ 12)个方块组成。他想在一些方块上种植美味的玉米给奶牛吃。不幸的是,其中一些方块不毛不育,不能种植作物。精明的约翰知道奶牛不喜欢彼此靠近,所以在选择要种植的方块时,他避免选择相邻的方块;没有两个被选择的方块共享一个边。他还没有最终决定要种植哪些方块。\u003c/p\u003e\u003cp\u003e作为一个非常开明的人,约翰希望考虑如何选择种植方块的所有可能选项。他如此开明,以至于将不选择任何方块也视为一种有效选项!请帮助约翰农场主确定他可以选择种植方块的方法数量。\u003c/p\u003e"}},{"title":"输入","value":{"format":"HTML","content":"第一行:两个以空格分隔的整数:\u003ci\u003eM\u003c/i\u003e 和 \u003ci\u003eN\u003c/i\u003e\r\u003cbr\u003e第2行..\u003ci\u003eM\u003c/i\u003e+1:第 \u003ci\u003ei\u003c/i\u003e+1 行描述了牧场的第 \u003ci\u003ei\u003c/i\u003e 行,包括 \u003ci\u003eN\u003c/i\u003e 个以空格分隔的整数,表示一个方块是否肥沃(1代表肥沃,0代表不毛不育)"}},{"title":"输出","value":{"format":"HTML","content":"第一行:一个整数,表示约翰农场主选择种植方块的方法数量,对100,000,000取模。"}},{"title":"示例","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2 3\r\n1 1 1\r\n0 1 0\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e9\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"提示","value":{"format":"HTML","content":"按以下方式对方块进行编号:\u003cbr\u003e\u003cpre\u003e1 2 3\u003cbr\u003e\u0026nbsp; 4 \u0026nbsp;\u003c/pre\u003e\r\u003cbr\u003e只有一种方式种植一个方块(1, 2, 3, 或 4),有三种方式种植两个方块(13, 14, 或 34),一种方式种植三个方块(134),以及一种方式不种植任何方块。4+3+1+1\u003d9。"}}]}