시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
15 초 64 MB 125 20 19 33.333%

문제

ZZ 함수의 정의는 다음과 같다.

\(ZZ(0,1) = a\)

\(ZZ(0,2) = b\)

\(ZZ(0,k) = ZZ(0,k-1) + ZZ(0,k-2); k > 2\)

\(ZZ(i,k) = \sum _{j=1} ^{k} {ZZ(i-1,j)} ; i \ge 1, k \ge 1\)

네 정수 a, b, c, d가 주어졌을 때, ZZ(c, d)를 찾는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T ≤ 200 가 주어진다. 

각 테스트 케이스는 네 정수 a, b, c, d로 이루어져 있다. (0 ≤ a, b ≤ 1 000 000 000, 1 ≤ c ≤ 100, 1 ≤ c x d ≤ 100 000 000)

출력

각 테스트 케이스마다 ZZ(c, d) mod 1 000 000 009를 출력한다. 

예제 입력 1

5
1 1 1 1
1 1 1 4
1 1 2 3
1 1 5 5
24995 8633 1 25158567

예제 출력 1

1
7
7
155
512203519
W3sicHJvYmxlbV9pZCI6IjkzNDEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJaWiIsImRlc2NyaXB0aW9uIjoiPHA+WlogXHVkNTY4XHVjMjE4XHVjNzU4IFx1YzgxNVx1Yzc1OFx1YjI5NCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHViMmU0LjxcL3A+XHJcblxyXG48cD5cXChaWigwLDEpID0gYVxcKTxcL3A+XHJcblxyXG48cD5cXChaWigwLDIpID0gYlxcKTxcL3A+XHJcblxyXG48cD5cXChaWigwLGspID0gWlooMCxrLTEpICsgWlooMCxrLTIpOyBrICZndDsgMlxcKTxcL3A+XHJcblxyXG48cD5cXChaWihpLGspID0gXFxzdW0gX3tqPTF9IF57a30ge1paKGktMSxqKX0gOyBpIFxcZ2UgMSwgayBcXGdlIDFcXCk8XC9wPlxyXG5cclxuPHA+XHViMTI0IFx1YzgxNVx1YzIxOCBhLCBiLCBjLCBkXHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFpaKGMsIGQpXHViOTdjIFx1Y2MzZVx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOCBUICZsZTsgMjAwIFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1YjEyNCBcdWM4MTVcdWMyMTggYSwgYiwgYywgZFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiZuYnNwOygwICZsZTsgYSwgYiAmbGU7IDEgMDAwIDAwMCAwMDAsIDEgJmxlOyBjICZsZTsgMTAwLCAxICZsZTsgYyB4IGQgJmxlOyAxMDAgMDAwIDAwMCk8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjljOFx1YjJlNCBaWihjLCBkKSZuYnNwO21vZCAxIDAwMCAwMDAgMDA5XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI5MzQxIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiWloiLCJkZXNjcmlwdGlvbiI6IjxwPlpaLWZ1bmN0aW9uLCBhIHNob3J0ZXIgbmFtZSBvZiBaZWVkWmFhZC1mdW5jdGlvbiBpcyBkZWZpbmVzIGFzIGZvbGxvd2VkLiZuYnNwOzxcL3A+XHJcblxyXG48cD5cXChaWigwLDEpID0gYVxcKTxcL3A+XHJcblxyXG48cD5cXChaWigwLDIpID0gYlxcKTxcL3A+XHJcblxyXG48cD5cXChaWigwLGspID0gWlooMCxrLTEpICsgWlooMCxrLTIpOyBrICZndDsgMlxcKTxcL3A+XHJcblxyXG48cD5cXChaWihpLGspID0gXFxzdW0gX3tqPTF9IF57a30ge1paKGktMSxqKX0gOyBpIFxcZ2UgMSwgayBcXGdlIDFcXCk8XC9wPlxyXG5cclxuPHA+R2l2ZW4gNCBpbnRlZ2VycyBhLCBiLCBjIGFuZCBkLiB5b3VyIHRhc2sgaXMgdG8gZmluZCBaWihjLCBkKS4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPkZpcnN0IGxpbmUgb2YgaW5wdXQgaXMgYSBudW1iZXIgb2YgdGVzdCBjYXNlcyBUICZsZTsgMjAwLiZuYnNwOzxcL3A+XHJcblxyXG48cD5FYWNoIHRlc3QgY2FzZSBpcyBhIGxpbmUgY29udGFpbmluZyBvZiA0IGludGVnZXJzIGEsIGIsIGMgYW5kIGQgKDAgJmxlOyBhLCBiICZsZTsgMSAwMDAgMDAwIDAwMCwgMSAmbGU7IGMgJmxlOyAxMDAsIDEgJmxlOyBjIHggZCAmbGU7IDEwMCAwMDAgMDAwKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSwgZGlzcGxheSBaWihjLCBkKSBtb2QgMSAwMDAgMDAwIDAwOS4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=