题目描述
有一个三个顶点做构成的三角形,给出最开始所在的点,一次移动只能移动到其他的两个点,求移动n次后,留在原点的所有方案数。
输入描述
每个测试用例的包含一个整数n(2 ≤ n ≤ 1000000)——移动的次数, w(1 ≤ w ≤ 3)——起始位置
输出描述
输出一个数——留在原点的所有方案数 由于答案很大,对1000000009取模
样例输入1
3 1
样例输出1
2
数据范围
2≤n≤1e6; 1 <= w <= 3;
有一个三个顶点做构成的三角形,给出最开始所在的点,一次移动只能移动到其他的两个点,求移动n次后,留在原点的所有方案数。
每个测试用例的包含一个整数n(2 ≤ n ≤ 1000000)——移动的次数, w(1 ≤ w ≤ 3)——起始位置
输出一个数——留在原点的所有方案数 由于答案很大,对1000000009取模
3 1
2
2≤n≤1e6; 1 <= w <= 3;