你来到了一个因为外部疫情而与外界隔离的高次元小区，小区内有 栋居民楼，居民楼有序号 ，每两个居民楼 之间都有一条独一无二的长度为的道路，整条道路边有连续的绿化隔离栅栏，栅栏每单位长度有 格。但是由于绿化（没有树）过少，当地居民一直想要将一部分道路旁种一些树，修成林荫小径，使得任意两个居民楼之间都可以由若干条林荫小径到达。考虑到美观性，树只能种在栅栏的格子里。一条路如果是林荫小径当且仅当这条路上（即两个楼之间）满足任意连续的 格栅栏至少有一棵树（如果不满 格则只需要种一棵树）。现在居民将这个提议交付给了当地居委会，但是居委会预算有限，他们只能种尽可能少的树来实现这个提议，他们希望知道他们有多少种不同的方案去实现这个提议。假设有两个方案，选中的道路分别为 , 两个方案不同当且仅当 或者存在道路 使得 且 。由于答案可能会很大，请将输出对 取模。

输入描述:

一行四个数字  ,  ,  分别如题 , 且保证 

输出描述:

一行一个数字， 表示满足题目要求的方案数，答案对  取模。

5 2 5

64

5 2 4

45

10000000 1 10000000

245968677

1000000 1000 1

595392237

备注:

对于样例一：

我们用表示从楼  到楼  的一条路

 长度为2，有4格，不足5格，可以种在第1格的位置，因此需要种1棵树

 长度为3，有6格，可以种在第5格的位置，因此需要种1棵树

 长度为4，有8格，可以种在第5格的位置，因此需要种1棵树

 长度为5，有10格，可以种在第5，10格的位置，因此需要种2棵树

此时我们可以在楼  之间取任意生成树，并且取任意边  连接生成树，即可得到答案，4个顶点的完全图有生成树共16个，故答案为 。

对于样例二：

 长度为2，有4格，可以种在第4格的位置，因此需要种1棵树

 长度为3，有6格，可以种在第4格的位置，因此需要种1棵树

 长度为4，有8格，可以种在第4，8格的位置，因此需要种2棵树

 长度为5，有10格，可以种在第4，8格的位置，因此需要种2棵树

此时我们可以在楼  之间取任意生成树，3个顶点的完全图有生成树共3个,然后可以选择以下三种情况

让楼4和楼相连，楼4和楼5相连，共3种；

让楼5和楼相连，楼4和楼5相连，共3种；

让楼4和楼相连，让楼4和楼相连，共9种。


故答案为 。