题目描述

你的后院是一个大小为 $\text{width}\times\text{height}$ 平方米的矩形网格。你希望种植 $\text{treeCount}$ 棵树，并满足以下规则：

• 所有树都必须种在网格内的整数坐标点上；
• 所有树必须位于同一条直线上；
• 任意两棵树之间的距离至少为 $\text{distance}$ 米。

例如，当网格大小为 $10\times10$、种植 $4$ 棵树且 $\text{distance}=2$ 时，下面给出了两种可行方案：

求满足条件的不同种植方案数，对 $1,000,000,000$ 取模。如果存在一个坐标点 $(x,y)$，某个方案在该点种了树而另一个方案没有，则这两个方案不同。

输入格式

一行输入四个整数 $\text{treeCount},\text{width},\text{height},\text{distance}$。

输出格式

输出满足条件的不同种植方案数，对 $1,000,000,000$ 取模后的结果。

样例输入

2 4 4 1

样例输出

300

数据范围

• $1\le\text{treeCount}\le50$；
• $1\le\text{width}\le500$；
• $1\le\text{height}\le500$；
• $1\le\text{distance}\le50$。