小 C 决定在他的花园里种出 字样的图案，因此他想知道 和 两个字母各自有多少种种花的方案；不幸的是，花园中有一些土坑，这些位置无法种花，因此他希望你能帮助他解决这个问题。
花园可以看作有 个位置的网格图，从上到下分别为第 到第 行，从左到右分别为第 列到第 列，其中每个位置有可能是土坑，也有可能不是，可以用 表示第 行第 列这个位置有土坑，否则用 表示这个位置没土坑。
一种种花方案被称为 形的，如果存在 ，以及 ，满足 ，并且 ，使得第 行的第 到第 列、第 行的第 到第 列以及第 列的第 到第 行都不为土坑，且只在上述这些位置上种花。
一种种花方案被称为 形的，如果存在 ，以及 ，满足 ，并且 ，使得第 行的第 到第 列、第 行的第 到第 列以及第 列的第 到第 行都不为土坑，且只在上述这些位置上种花。
样例一解释中给出了 形和 形种花方案的图案示例。
现在小 C 想知道，给定 以及表示每个位置是否为土坑的值 ， 形和 形种花方案分别有多少种可能？由于答案可能非常之大，你只需要输出其对 取模的结果即可，具体输出结果请看输出格式部分。