hard 和 easy 的唯二的区别为 小羊变成大羊需要花费时间 以及 数据的范围。

我的世界有动物繁殖系统，只需对着两只羊各喂下一个小麦，就会生出一个羊宝宝。

大羊生出来的小羊会等待 q min 长成大羊才可以繁殖，同一头羊繁殖前后也需要 k min 的时间间隔，繁殖必须要求两头羊。

如果小麦无限，请你求出在规定时间内最多的总共的羊数。

第一行两个整数 n ( 1 <= n <= 10³ ) ,q ( 1 <= q <= 10⁶ )和 k ( 1 <= k <= 10⁶ ) 表示 初始有多少羊 和 繁殖的时间间隔。

第二行一个整数 t 表示规定的时间（单位为 min，题目保证 1 <= t <= 10⁶, t/k <= 16）。

输出一个整数 s，表示总共的羊数。

数据保证答案在 64 位整数范围内。