题目描述

有一个三个顶点做构成的三角形，给出最开始所在的点，一次移动只能移动到其他的两个点，求移动n次后，留在原点的所有方案数。

输入描述

每个测试用例的包含一个整数n(2 ≤ n ≤ 1000000)——移动的次数， w(1 ≤ w ≤ 3)——起始位置

输出描述

输出一个数——留在原点的所有方案数 由于答案很大，对1000000009取模

样例输入1

3 1

样例输出1

2

数据范围

2≤n≤1e6; 1 <= w <= 3;