题号：NC214799
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
Bear_2有一串n个珠子组成的手链，手链上珠子按顺序编号为 0 到 n-1 。一开始0号珠子朝上戴在Bear_2的手上，每天Bear_2 会等概率拨动 0到K 颗珠子(例如，手链由 5 颗珠子构成，Bear_2拨动 3 颗珠子，如果拨动前 1 号珠子朝上，那么拨动后 4 号珠子朝上，如果拨动前 2 号珠子朝上，那么拨动后 0 号珠子朝上)。
请问，D 天后 X 号珠子朝上的概率，模1e9+7。
输入描述:
多组输入
每组的数据，第一行内输入四个正整数 n,D,K,X(1<n<=100,1<=D<=109,0<K,X<n) ，含义如上
输出描述:
对于每组测试数据，在一行内输出 X 号珠子朝上的概率，答案模1e9+7
示例1
输出
复制
500000004
500000004
309570315