小蓝在旅游时看到了景点里有一块石头。这块石头承载了一个传说。
传说在很久以前有一对爱人在战乱时期分散，历经苦难在几年后重逢，为了纪念这段经历，他们在一块石头上留下了两道刻痕。每一道刻痕都是水平或垂直于地面的线段（注意刻痕可能长度为 ），刻痕长度为正整数。
经过了多年的风化，这块石头已经变得坑坑洼洼，没法再判断当年的两道刻痕的位置，但小蓝从导游那里得知，当年的两道刻痕并不相交，两条刻痕的线段不存在公共点（包括端点）。
小蓝现在希望知道，两道刻痕的位置有多少种不同的可能。特别地：
- 当刻痕长度为 时，不区分水平和垂直方向，同一位置 的刻痕仅算 种可能；
- 两道刻痕的顺序不同视为不同的可能（例如刻痕 A 在前、刻痕 B 在后，与刻痕 B 在前、刻痕 A 在后视为两种不同情况）。
本题中，石头用一个 的 矩阵来表示，若一个位置为 则表示它不能为刻痕占据的位置，为 则表示它可能是刻痕占据的位置。一条刻痕对应矩阵中宽为 的水平或垂直的线段，且在矩阵中的对应位置必须全部为 ：水平刻痕的同一行中，起点到终点之间（包括端点）位置上的值在矩阵中均为 ；垂直刻痕的同一列中，起点到终点之间（包括端点）位置上的值在矩阵中均为 。
