O神

题目描述

Orange迷上了一款由M学长研发的开放世界游戏O神，在O神中，祈愿是一种用于获取角色和武器的方式（实际上就是抽卡），从卡池中，我们可以获得不同星级的武器和角色，最低为3星(垃圾)，最高为5星。同时5星产物也分为UP5星和常驻5星。在游戏中，由于某种神秘力量的限制，我们的祈愿有如下规则:

我们的每10次祈愿中一定会有比3星更高品质的产物（4星，常驻5星或者UP5星）
我们的每90次祈愿中一定会有比4星更高品质的产物（常驻5星或者UP5星）
常驻5星不会连续出现，但是UP5星可以（或者说，每次获得常驻5星后，下一个5星品质的产物一定是UP5星，但是每次获得UP5星后，下一个5星品质的产物可能是UP5星，也可能是常驻5星）

上述规则我们称为 保底机制，我们将祈愿获得非UP5星的结果称为 歪，由于Orange在抽某位强力角色时，连续歪了7次，以至于Orange十分红温，他开始怀疑M学长在设计游戏祈愿时，并没有按照规则设计保底机制，因此，Orange想请你写一个程序，用来判定M学长的保底机制是否正确。

一个仅包含 $\{3,4,5,U\}$ 的字符串 $s（ len(s) \leq 10^6 ）$ ，表示Orange的抽卡记录，其中 $3$ 表示3星产物， $4$ 表示4星产物， $5$ 表示常驻5星， $U$ 表示UP5星。

$len(s)$ 表示字符串s的长度

你只需要输出 valid 或者 invalid ，表示抽卡记录是否合法

433333333334

invalid