triangle

题目描述

一个无限行的数字三角形，第 $i$ 行有 $i$ 个数。第一行的第一个数是 $1$ ，其他的数满足如下关系：如果用 $F[i][j]$ 表示第 $i$ 行的第 $j$ 个数，那么 $F[i][j]=A*F[i-1][j]+B*F[i-1][j-1]$ （不合法的下标的数为 $0$ ）。

当 $A=2, B=3$ 时的数字三角形的前 $5$ 行为：

1

2 3

4 12 9

8 36 54 27

16 96 216 216 81

现在有 $T$ 次询问，求 $A=a, B=b$ 时数字三角形的第 $n$ 行第 $m$ 个数的值模 $10^9+9$ 的结果。

输入格式

第一行为一个整数 $T$ 。

接下一共 $T$ 行，每行四个整数 $a, b, n, m$ 。

输出格式

一共 $T$ 行，每行一个整数，表示那个位置上的数的值。

样例

输入

2
2 3 3 3
3 1 4 1

输出

9
27

数据范围

$n, T \leq 100000, 1 \leq m \leq n, 0 \leq a,b \leq 10^9$ 。

Subtask1 ($20\%$) ： $n, T \leq 100$ 。

Subtask2 ($20\%$) ： $n \leq 10000, T \leq 1000$

Subtask3 ($60\%$) ：无特殊限制。