你有一个大小为 n\times n 的矩阵，矩阵每个格子有一个颜色 a_{i,j}\le n。

你在网上闲逛的时候，发现有文章提到等差数列。

乌龟棋的棋盘是一行 N 个格子，每个格子上一个分数（非负整数）。棋盘第 1 格是唯一的起点，第 N 格是终点，游戏要求玩家控制一个乌龟棋子从起点出发走到终点。

Kiana 最近沉迷于一款神奇的游戏无法自拔。

某大学有 n 个职员，编号为 1\ldots n。

小 A 的工作不仅繁琐，更有苛刻的规定，要求小 A 每天早上在 6:00 之前到达公司，否则这个月工资清零。可是小 A 偏偏又有赖床的坏毛病。于是为了保住自己的工资，小 A 买了一个空间跑路器，每秒钟可以跑 2^k 千米（k 是任意自然数）。当然，这个机器是用 longint 存的，所以总跑路长度不能超过 maxlongint 千米。小 A 的家到公司的路可以看做一个有向图，小 A 家为点 1，公司为点 n，每条边长度均为一千米。小 A 想每天能醒地尽量晚，所以让你帮他算算，他最少需要几秒才能到公司。数据保证 1 到 n 至少有一条路径。

在 N \times N 的棋盘里面放 K 个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共 8 个格子。 对于全部数据，1 \le N \le 9，0 \le K \le N\times N。

A 国有 n 座城市，编号从 1 到 n，城市之间有 m 条双向道路。每一条道路对车辆都有重量限制，简称限重。