문제
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)를 찾는 프로그램을 작성하시오.
출력
각 테스트 케이스마다 ZZ(c, d) mod 1 000 000 009를 출력한다.
예제 출력 1
1
7
7
155
512203519
W3sicHJvYmxlbV9pZCI6IjkzNDEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJaWiIsImRlc2NyaXB0aW9uIjoiPHA+WlogXHVkNTY4XHVjMjE4XHVjNzU4IFx1YzgxNVx1Yzc1OFx1YjI5NCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHViMmU0LjxcL3A+XHJcblxyXG48cD5cXChaWigwLDEpID0gYVxcKTxcL3A+XHJcblxyXG48cD5cXChaWigwLDIpID0gYlxcKTxcL3A+XHJcblxyXG48cD5cXChaWigwLGspID0gWlooMCxrLTEpICsgWlooMCxrLTIpOyBrICZndDsgMlxcKTxcL3A+XHJcblxyXG48cD5cXChaWihpLGspID0gXFxzdW0gX3tqPTF9IF57a30ge1paKGktMSxqKX0gOyBpIFxcZ2UgMSwgayBcXGdlIDFcXCk8XC9wPlxyXG5cclxuPHA+XHViMTI0IFx1YzgxNVx1YzIxOCBhLCBiLCBjLCBkXHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFpaKGMsIGQpXHViOTdjIFx1Y2MzZVx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOCBUICZsZTsgMjAwIFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1YjEyNCBcdWM4MTVcdWMyMTggYSwgYiwgYywgZFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiZuYnNwOygwICZsZTsgYSwgYiAmbGU7IDEgMDAwIDAwMCAwMDAsIDEgJmxlOyBjICZsZTsgMTAwLCAxICZsZTsgYyB4IGQgJmxlOyAxMDAgMDAwIDAwMCk8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjljOFx1YjJlNCBaWihjLCBkKSZuYnNwO21vZCAxIDAwMCAwMDAgMDA5XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiI5MzQxIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiWloiLCJkZXNjcmlwdGlvbiI6IjxwPlpaLWZ1bmN0aW9uLCBhIHNob3J0ZXIgbmFtZSBvZiBaZWVkWmFhZC1mdW5jdGlvbiBpcyBkZWZpbmVzIGFzIGZvbGxvd2VkLiZuYnNwOzxcL3A+XHJcblxyXG48cD5cXChaWigwLDEpID0gYVxcKTxcL3A+XHJcblxyXG48cD5cXChaWigwLDIpID0gYlxcKTxcL3A+XHJcblxyXG48cD5cXChaWigwLGspID0gWlooMCxrLTEpICsgWlooMCxrLTIpOyBrICZndDsgMlxcKTxcL3A+XHJcblxyXG48cD5cXChaWihpLGspID0gXFxzdW0gX3tqPTF9IF57a30ge1paKGktMSxqKX0gOyBpIFxcZ2UgMSwgayBcXGdlIDFcXCk8XC9wPlxyXG5cclxuPHA+R2l2ZW4gNCBpbnRlZ2VycyBhLCBiLCBjIGFuZCBkLiB5b3VyIHRhc2sgaXMgdG8gZmluZCBaWihjLCBkKS4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPkZpcnN0IGxpbmUgb2YgaW5wdXQgaXMgYSBudW1iZXIgb2YgdGVzdCBjYXNlcyBUICZsZTsgMjAwLiZuYnNwOzxcL3A+XHJcblxyXG48cD5FYWNoIHRlc3QgY2FzZSBpcyBhIGxpbmUgY29udGFpbmluZyBvZiA0IGludGVnZXJzIGEsIGIsIGMgYW5kIGQgKDAgJmxlOyBhLCBiICZsZTsgMSAwMDAgMDAwIDAwMCwgMSAmbGU7IGMgJmxlOyAxMDAsIDEgJmxlOyBjIHggZCAmbGU7IDEwMCAwMDAgMDAwKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSwgZGlzcGxheSBaWihjLCBkKSBtb2QgMSAwMDAgMDAwIDAwOS4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d