正交二叉树

时间限制：1000ms

空间限制：1024MB

题目描述

在平面直角坐标系中生长着一种奇妙的二叉树，它的所有的分叉和叶子都是整点。而且它所有的枝条长度都是一，并且每个枝条与子代的枝条垂直。

具体的来说，第一代，我们只有一个根节点位于 $(0,0)$ ；第二代，从根节点生出子代节点 $(-1,0)$ 和 $(1,0)$ ；第三代，从 $(-1,0)$ 也要产生两个子代节点，并且新的边要和边 $(0,0)$ 到 $(-1,0)$ 垂直，因此只能是 $(-1,1)$ 和 $(-1,-1)$ ，同理 $(1,0)$ 的子节点是 $(1,-1)$ 和 $(1,1)$ 。接下来每一代重复第三代的操作，我们就能得道第 $n$ 代的正交二叉树。

不难发现，正交二叉树的节点在同一格子上是会出现重叠的。现在需要你来计算一下第 $n$ 代时，某一个整点上有多少个正交二叉树的节点重叠在一起。

输入格式

三个整数 $n,x,y$ ，表示第 $n$ 代的正交二叉树在 $(x,y)$ 处有多少个节点重叠。

输出格式

一个整数表示答案，由于答案可能很大，请对 $100009$ 取模。

样例输入1

4 0 1

样例输出1

2

样例1解释

从根节点到叶子节点的坐标为 $(0,0)$ ; $(-1,0)$ , $(1,0)$ ; $(-1,1)$ , $(-1,-1)$ , $(1,-1)$ , $(1,1)$ ; $(0,1)$ , $(-2,1)$ , $(-2,-1)$ , $(0,-1)$ , $(0,-1)$ , $(2,-1)$ , $(2,1)$ , $(0,1)$ 。不难发现只有两个节点在 $(0,1)$ 处。

数据范围及约定

$n\leq600$, $x,y$ 属于 $[-300,300]$