#P18800. [POI1998] 画室

[POI1998] 画室

[POI1998] 画室

题目描述

画室用带孔的正方形模板印制图案。第 ii 级模板有 2i2^i 行、2i2^i 列,每个位置要么有孔,要么没有孔。

第 00 级模板只有一个位置,这个位置有孔。对于 i>0i>0,将第 ii 级模板分成四个同样大小的正方形:左上部分没有孔,右上、左下、右下三部分分别是完整的第 i−1i-1 级模板。

将两张第 nn 级模板完全重合,再把上面的一张向右移动 xx 列、向上移动 yy 行。只有上下两张模板的孔恰好重合的位置,颜料才能穿过。

求有多少个位置能让颜料穿过。模板外部没有孔;移动后只考虑两张模板的重叠部分。

输入格式

第一行一个整数 nn。

第二行一个整数 xx,第三行一个整数 yy。

0≤n≤1000\le n\le100,0≤x,y≤2n0\le x,y\le2^n。x,yx,y 均以十进制给出。

输出格式

输出一个整数,表示重合的孔数。答案可能超过 64 位整数范围。

样例输入

2
2
2

样例输出

3