题目描述

徐老师最近刚学完广度优先搜索$(bfs)$，知道了广搜在一个矩阵上的探索模式是像波纹一样一层层向周围扩散

void bfs(int sx, int sy){
    queue<Node> q;
    q.push(Node{sx, sy});
    while (!q.empty()){
        Node now = q.front();
        q.pop();
        for (int i = 0; i < 4; ++i){
            int tx = now.x + dirx[i];
            int ty = now.y + diry[i];
            if (vis[tx][ty] == 0){
                q.push(Node{tx, ty});
                vis[tx][ty] = 1;
            }
        }
    }
}

但是显然徐老师的这段代码有一个致命错误——没有判断边界，也就是会无限向外拓展

比如有如下大小的矩阵，用 0 表示没走过的点($vis[x][y] == 0$)，用 1 表示走过的点($vis[x][y] == 1$)

第一轮搜索以后矩阵如下

0000000
0000000
0001000
0000000
0000000

第二轮搜索以后矩阵如下

0000000
0001000
0011100
0001000
0000000

第三轮搜索以后矩阵如下

0001000
0011100
0111110
0011100
0001000

现在徐老师想知道，现在他这份没有设置范围的代码，在不考虑越界（即认为 $vis$ 数组无穷大，代码不会因为出界报错）的情况下

第 $n$ 轮搜索以后 $vis$ 数组求和的结果是多少？

输入格式

本题采用文件读写。

• 读入文件名：bfs.in
• 写出文件名：bfs.out

输入第一行是一个整数 $n$，表示搜索的轮数

输出格式

输出一行，包含一个整数，表示答案

样例

3

13

1000000000

1999999998000000001

数据范围与提示

• 对于 $50\%$ 的数据，保证 $1 \leq n \leq 20$

• 对于 $80\%$ 的数据，保证 $1 \leq n \leq 10000$

• 对于 $100\%$ 的数据，保证 $1 \leq n \leq 10^9$