题目描述
hard 和 easy 的唯二的区别为 小羊变成大羊需要花费时间 以及 数据的范围。
我的世界有动物繁殖系统，只需对着两只羊各喂下一个小麦，就会生出一个羊宝宝。
大羊生出来的小羊会等待 q min 长成大羊才可以繁殖，同一头羊繁殖前后也需要 k min 的时间间隔，繁殖必须要求两头羊。
如果小麦无限，请你求出在规定时间内最多的总共的羊数。
输入
第一行两个整数 n ( 1 <= n <= 103 ) ,q ( 1 <= q <= 106 )和 k ( 1 <= k <= 106 ) 表示 初始有多少羊 和 繁殖的时间间隔。
第二行一个整数 t 表示规定的时间（单位为 min，题目保证 1 <= t <= 106, t/k <= 16）。
输出
输出一个整数 s，表示总共的羊数。
数据保证答案在 64 位整数范围内。