using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
static string InputPattern = "InputX";
static List<string> GetInputList()
{
var WillReturn = new List<string>();
if (InputPattern == "Input1") {
WillReturn.Add("2 3");
WillReturn.Add("10 10 20");
WillReturn.Add("10 10 20");
//3
}
else if (InputPattern == "Input2") {
WillReturn.Add("1 4");
WillReturn.Add("2 1 1 2");
//2
}
else if (InputPattern == "Input3") {
WillReturn.Add("3 3");
WillReturn.Add("2 9 4");
WillReturn.Add("7 5 3");
WillReturn.Add("6 1 8");
//2
}
else if (InputPattern == "Input4") {
WillReturn.Add("1 1");
WillReturn.Add("10000");
//0
}
else {
string wkStr;
while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
}
return WillReturn;
}
static long[] GetSplitArr(string pStr)
{
return (pStr == "" ? new string[0] : pStr.Split(' ')).Select(pX => long.Parse(pX)).ToArray();
}
static long[,] mBanArr;
static long UB_X;
static long UB_Y;
static long[,] mRunSumArr;
static void Main()
{
List<string> InputList = GetInputList();
mBanArr = CreateBanArr(InputList.Skip(1));
UB_X = mBanArr.GetUpperBound(0);
UB_Y = mBanArr.GetUpperBound(1);
mRunSumArr = (long[,])mBanArr.Clone();
// 累積和を設定する (横方向)
for (long LoopX = 1; LoopX <= UB_X; LoopX++) {
for (long LoopY = 0; LoopY <= UB_Y; LoopY++) {
mRunSumArr[LoopX, LoopY] += mRunSumArr[LoopX - 1, LoopY];
}
}
// 累積和を設定する (縦方向)
for (long LoopX = 0; LoopX <= UB_X; LoopX++) {
for (long LoopY = 1; LoopY <= UB_Y; LoopY++) {
mRunSumArr[LoopX, LoopY] += mRunSumArr[LoopX, LoopY - 1];
}
}
var Stk = new Stack<JyoutaiDef>();
JyoutaiDef WillPush;
WillPush.CurrX = 0;
WillPush.CurrY = 0;
WillPush.YokoRangeInfoList = new List<RangeInfoDef>();
WillPush.TateRangeInfoList = new List<RangeInfoDef>();
Stk.Push(WillPush);
long Answer = 0;
while (Stk.Count > 0) {
JyoutaiDef Popped = Stk.Pop();
// クリア判定
if (Popped.CurrX > UB_X && Popped.CurrY > UB_Y) {
if (Popped.YokoRangeInfoList.Count * Popped.TateRangeInfoList.Count >= 2) {
Answer++;
}
continue;
}
bool WillDevideYoko = false;
if (Popped.YokoRangeInfoList.Count == 0) {
WillDevideYoko = true;
}
if (Popped.TateRangeInfoList.Count >= 1 && Popped.CurrX <= UB_X) {
WillDevideYoko = true;
}
if (WillDevideYoko) {
for (long I = Popped.CurrX; I <= UB_X; I++) {
RangeInfoDef WillAdd;
WillAdd.RangeSta = Popped.CurrX;
WillAdd.RangeEnd = I;
WillPush.CurrX = I + 1;
WillPush.CurrY = Popped.CurrY;
WillPush.YokoRangeInfoList = new List<RangeInfoDef>(Popped.YokoRangeInfoList);
WillPush.YokoRangeInfoList.Add(WillAdd);
WillPush.TateRangeInfoList = Popped.TateRangeInfoList;
if (IsValid(WillPush.YokoRangeInfoList, WillPush.TateRangeInfoList)) {
Stk.Push(WillPush);
}
}
}
else {
for (long I = Popped.CurrY; I <= UB_Y; I++) {
RangeInfoDef WillAdd;
WillAdd.RangeSta = Popped.CurrY;
WillAdd.RangeEnd = I;
WillPush.CurrX = Popped.CurrX;
WillPush.CurrY = I + 1;
WillPush.YokoRangeInfoList = Popped.YokoRangeInfoList;
WillPush.TateRangeInfoList = new List<RangeInfoDef>(Popped.TateRangeInfoList);
WillPush.TateRangeInfoList.Add(WillAdd);
if (IsValid(WillPush.YokoRangeInfoList, WillPush.TateRangeInfoList)) {
Stk.Push(WillPush);
}
}
}
}
Console.WriteLine(Answer);
}
static long CalledCnt = 0;
// 確定した分割ごとの総和が等しいかを判定
static bool IsValid(List<RangeInfoDef> pYokoRangeInfoList, List<RangeInfoDef> pTateRangeInfoList)
{
var AreaSet = new HashSet<long>();
foreach (RangeInfoDef EachYokoRangeInfo in pYokoRangeInfoList) {
foreach (RangeInfoDef EachTateRangeInfo in pTateRangeInfoList) {
long StaX = EachYokoRangeInfo.RangeSta;
long EndX = EachYokoRangeInfo.RangeEnd;
long StaY = EachTateRangeInfo.RangeSta;
long EndY = EachTateRangeInfo.RangeEnd;
long CurrArea = DeriveSumRect(StaX, StaY, EndX, EndY);
AreaSet.Add(CurrArea);
if (AreaSet.Count >= 2) {
return false;
}
}
}
return true;
}
struct JyoutaiDef
{
internal long CurrX;
internal long CurrY;
internal List<RangeInfoDef> YokoRangeInfoList;
internal List<RangeInfoDef> TateRangeInfoList;
}
struct RangeInfoDef
{
internal long RangeSta;
internal long RangeEnd;
}
// (pStaX,pStaY)と(pEndX,pEndY)からなる長方形の数の和を返す
static long DeriveSumRect(long pStaX, long pStaY, long pEndX, long pEndY)
{
long CurrSum = DeriveSumRectHelper(pEndX, pEndY);
CurrSum -= DeriveSumRectHelper(pStaX - 1, pEndY);
CurrSum -= DeriveSumRectHelper(pEndX, pStaY - 1);
CurrSum += DeriveSumRectHelper(pStaX - 1, pStaY - 1);
return CurrSum;
}
// (0,0)と(pX,pY)からなる長方形の数の和を返す
static long DeriveSumRectHelper(long pX, long pY)
{
if (pX < 0) return 0;
if (pY < 0) return 0;
return mRunSumArr[pX, pY];
}
////////////////////////////////////////////////////////////////
// IEnumerable<string>をlongの2次元配列に設定
////////////////////////////////////////////////////////////////
static long[,] CreateBanArr(IEnumerable<string> pStrEnum)
{
var StrList = new List<string>(pStrEnum);
if (StrList.Count == 0) {
return new long[0, 0];
}
long[] LongArr = { };
Action<string> SplitAct = pStr =>
LongArr = pStr.Split(' ').Select(pX => long.Parse(pX)).ToArray();
SplitAct(StrList[0]);
long UB_X = LongArr.GetUpperBound(0);
long UB_Y = StrList.Count - 1;
long[,] WillReturn = new long[UB_X + 1, UB_Y + 1];
for (long Y = 0; Y <= UB_Y; Y++) {
SplitAct(StrList[(int)Y]);
for (long X = 0; X <= UB_X; X++) {
WillReturn[X, Y] = LongArr[X];
}
}
return WillReturn;
}
}