#P18171. Sugar Sweet 3
Sugar Sweet 3
Sugar Sweet 3
Pibi、Prof. Peng 和 Emperor Bie 正在玩一个纸牌游戏。三人分别持有 张类型 1 的牌、 张类型 2 的牌和 张类型 3 的牌。桌上的牌堆最初为空。
游戏共进行 轮。每轮选择一名手中还有牌的玩家,由他打出一张牌:
- 如果牌堆为空,或牌堆中的牌与打出的牌类型相同,就把打出的牌放入牌堆。
- 否则,从牌堆中取走一张牌,与本轮打出的牌一起丢弃。
因此,在任意时刻,非空牌堆里的牌始终属于同一种类型。
例如,三人持牌数分别为 ,依次由类型为 的玩家出牌,则每轮结束后的牌堆依次为
$$[1],\quad [],\quad [2],\quad [],\quad [3],\quad [].$$设整个游戏结束后牌堆为空,且在全部轮次结束时,牌堆一共出现了 次空的状态。即统计所有满足 、第 轮结束后牌堆为空的时刻;初始的空牌堆不计入次数,最后一轮的空状态计入。
这样的游戏会使三人得到 袋糖,其中 是预先给定的常数。如果游戏结束后牌堆非空,则得到 0 袋糖。
求所有不同游戏得到的糖袋数之和,对 取模。两个游戏不同,当且仅当至少一轮的出牌玩家不同;同一玩家手中的牌不区分个体。
输入格式
一行四个整数 ,满足
$$1\le A,B,C\le1000,\qquad A+B+C\le1000,\qquad1\le x\le10^9.$$输出格式
输出一个整数,表示所有游戏的糖袋数之和模 的结果。
样例 1
输入:
1 2 3 1
输出:
110
这个样例中,最终牌堆为空且 的游戏分别有 6、16、24 种。因此答案为
样例 2
输入:
4 5 7 12
输出:
881078346