题目修改

19:24 题面样例更正

19:52 题面样例更正

题目背景

新一期的周赛又要到了，天天摸鱼的周某才忽然意识到比赛的到来，看着洛谷一个月三题的记录，他感到非常焦虑。赛前晚上翻来覆去难以入眠。

第二天，他战战兢兢的打开了电脑，看到了这周的试题。他喜欢按顺序做题目，于是从第一题开始慢慢做了下去。接二连三的难题让他更加焦虑了。还好，这些难题中，夹杂着几道简单题，才让他稍微缓解了点压力。 他自认心理承受能力还算比较强，但再强终究是有个限度的。如果焦虑值超过了这个限度，他就会崩溃。

题目描述

为了方便计算，我们把周某人的焦虑具体为一个数值，考试前一天晚上，他的焦虑值是 $50$ 。 他开始就告诉了你他的做题水平。每一题题目都有一个难度，如果难度超过了他的做题水平，他就不会做了。 在比赛时你发现了一个规律，如果出现一题他会做的题，他的焦虑值就会减少 $20$ 。遇到不会做的题目比较特殊，如果有一题不会，他的焦虑就会上升基准值 $10$ 乘以一个权重后的值。你还发现，连续几题不会做，对应每道题的权重与斐波那契数列还有一个参数 $s$ 有关。举个例子，一道题不会，第一题权重为斐波那契数列的第 $s$ 项 ，他的焦虑上升 $10 \times$ 斐波那契数列的第 $s$ 项，并且对一个模数 $mod$ 进行取模 ，模数为 $10^{9}+7$ 。若连续两题不会，则两题权重分别为斐波那契数列的第 $s$ 项 , $2s$ 项分别对 $mod$ 取模 ，如果遇到了会做的题，则之前连续不会的题数量将清零。以此类推。

他告诉了你这么多，那么现在就请你帮他算算他的焦虑值吧！如果他承受住了这些焦虑，就输出他考完后到底有多焦虑。如果超过了心理承受限度，就赶紧帮他打个120送他去医院吧！。

注意！他做题喜欢严格按着顺序做，他非常讨厌跳题做。还有，如果比赛时的任何时候周某的焦虑值超过了承受限度，他就会立刻崩溃并拒绝继续做下去。还有，他的焦虑值是一个非负数，也就是说不可能小于 $0$ 。（毕竟做题不会越做越开心）例如现在焦虑值是 $10$ ，如果遇到了一题会做的题目那么做完后他的焦虑值会是 $0$ 而不是 $-10$。最后输出答案时也要对 $mod$ 取模 。注意 $mod = 10^{9}+7$

输入格式

输入共两行。 第一行包括四个整数 $n$ , $m$ , $k$ , $s$。分别表示题目的数量和他的水平以及周某的心里承受限度。 第二行有 $n$ 个整数 $x$ 分别表示每一题的难度。

输出格式

输出仅一行。如果周某没崩溃就输出他的焦虑值。如果崩溃了则输出 $120!$ ，还有停止做题时的焦虑程度。

样例

5 10 100 1
13 12 8 6 15

40

5 10 100 2
13 19 17 14 4

120!
170

大样例

见附加文件 zyc*.in 与 zyc*.out 。

下载链接：zyc

数据规模与约定

对于前 $40$% 的数据满足 $n$ $\le$ $1 \times 10^{5}$ ， $s$ $\le$ $50$。

对于 $100$% 的数据满足 $n$ $\le$ $5 \times 10^{5}$ ， $s$ $\le$ $1 \times 10^{15}$ ， $m$ ，$k$ ， $x$ $\le$ $1 \times 10^{15}$ 。