P7015: 普莱纳（Planina）
传统题
1.000s
时间限制
128MB
内存限制
3 提交
1 解决
【题目描述】
【题目描述】米尔科和斯拉夫科正在拍摄一部改编自科幻小说《太空少女13》的电影。剧本要求他们呈现很多不同的世界，所以他们决定在绿屏前拍摄整部电影，稍后再添加CGI背景。米尔科听说，生成人工地形的最佳方法是使用中点位移算法。
为了开始算法，Mirko选择4个点形成一个完美的正方形。然后执行以下步骤：
1.在正方形的每一边，他都在边的正中间添加一个新点。这个新点的高度是这一侧两点的平均高度。
2.在正方形的精确中心，他添加了一个新点，其高度是所有4个正方形顶点的平均高度，加上一个小的随机值。
完成这两个步骤后，他现在有了4个新的方块。他在新创建的正方形上重复同样的步骤，直到他对结果满意为止。
图1：算法的两次迭代
米尔科注意到，有些点属于不止一个正方形。为了减少内存消耗，他只计算和存储一次这样的点。他现在想知道，在N次迭代之后，总共需要在内存中存储多少点。
【输入格式】
第一行也是唯一一行输入包含一个整数N（1<N≤15），即迭代次数。
【输出格式】
第一行也是唯一一行输出应该包含一个数字，即N次迭代后存储的点数。
【样本输入1】
1
【样本输出1】
9
【样本输入2】
2
【样本输出2】
25
【样本输入3】
5
【样本输出3】
1089