В одном далеком-предалеком королевстве живет жадный-прежадный король. Для защиты своих владений он построил n сторожевых башен. Помимо башен, в королевстве есть две армии, во главе каждой из которых стоит властный и самодовольный генерал. Генералы терпеть не могут друг друга, в частности, они никогда не допустят, чтобы в одной из башен находились солдаты обеих армий.

Во время оборонительных действий для управления сторожевой башней генералу необходимо направить часть своей армии в эту башню. Каждый генерал требует у короля гонорар за управление башнями. Поскольку они живут в действительно очень далеком королевстве, каждый генерал оценивает свой гонорар следующим странным образом: он находит две самые удаленные башни, в которых находятся солдаты его армии и требует гонорар, равный этому расстоянию. Каждую башню можно считать точкой на плоскости с координатами (x, y), а расстояние между двумя точками с координатами (x₁, y₁) и (x₂, y₂) определяется в этом королевстве как |x₁ - x₂| + |y₁ - y₂|.

Жадного короля не совсем устроило такое требование генералов, поэтому он лишь согласился выплатить один гонорар на двоих генералов, равный максимальному из запрашиваемых двух гонораров. Однако, жадность все еще не дает покоя королю, поэтому из всех таких распределений башен между армиями, он хочет отыскать наиболее дешевое. Каждая башня должна быть занята солдатами ровно одной армии.

Для этих целей он нанял Вас. Вам необходимо найти минимальное количество денег, которое хватит для оплаты гонорара. А так как король еще крайне щепетилен, вы должны посчитать количество распределений, которые стоят такой же суммы денег. Поскольку их число может быть крайне велико, королю достаточно знать его значение в виде остатка от деления на 10⁹ + 7.

Два распределения называются различными, если различаются множества башен, занятых солдатами первого генерала.