Cannon

题号：NC223267
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

ZYT found a chessboard with two rows and $10^{1000}$ columns, and there are some cannons in it - ${x}$ cannons in the first row and ${y}$ in the second row.

In Chinese Chess, if a cannon and another piece (let’s call it A) are in the same row or column, and there is exactly one other piece in between, this cannon can capture A and move to A's original position.(In this problem, in order to keep the situation simple, we think that a cannon can capture any piece except itself, without considering which side it belongs to. )

Now, ZYT has performed a series of operations on these cannons. Define an operation $(l_i,a_i,b_i)$ as the ${a_{i}} ^{th}$ cannon currently counting from left to right in the ${l_{i}}^{th}$ row has eaten the ${b_{i}} ^{th}$ cannon of the same row, where $1\leq a_i,b_i\leq c,|a_i-b_i|= 2,l\in\{1,2\}$ ( ${c}$ is the number of cannons in this row). Define an operation sequence as an ordered arrangement of a series of operations.

ZYT wants to get many different sequences of operations. He is bored, so he wants to know how many different operation sequences can be generated for ${i}$ operations.

Specifically, he wants to know how many different operation sequences can be generated for i times under the following two rules:

ZYT can perform any operation that meets the above rules.
In all operations performed by ZYT, there are no two integers ${p,q}$ , satisfying $1\leq p<q\leq i$ and $l_p>l_q$ .

Since ZYT didn’t want to see a lot of output data, he asked to output the answer in the following way: For each question, let $f_i$ be the number of legal operation sequences obtained by operating ${i}$ times modulo $10^9+9$ .Please output $f_0\oplus f_1\oplus \cdots \oplus f_{x+y-4}$ , where $\oplus$ represents an exclusive OR operation.

输入描述:

The input consists one line containing two integers  and .

输出描述:

Output one line, containing two integers, representing the answers under the first and second rules.

示例1

输入

复制

3 4

输出

复制

47 7

示例2

输入

复制

5 6

输出

复制

802231 10919

示例3

输入

复制

14 14

输出

复制

522071256 509921384

示例4

输入

复制

100 100

输出

复制

366419165 27289129

备注:

For all test cases, it is guaranteed that .