U387185 【MC系列8】沉船宝藏
题目背景
## 题目提供者：[liu3600](https://www.luogu.com.cn/user/750365)
### liu3600 正在一个特别肥的沉船里找宝藏。
~~具体的自己去看题目描述~~
题目描述
传说很遥远的沉船顶层藏着诱人的宝藏。liu3600 历尽千辛万苦终于找到传说中的这个沉船，沉船的门口竖着一个告示牌，上面写有几个大字：寻宝说明书。说明书的内容如下：[](7)
此沉船共有 $N+1$ 层，最上面一层是顶层，顶层有一个房间里面藏着宝藏。除了顶层外，沉船另有 $N$ 层，每层 $M$ 个房间，这 $M$ 个房间围成一圈并按逆时针方向依次编号为 $0,…,M-1$。其中一些房间有通往上一层的楼梯，每层楼的楼梯设计可能不同。每个房间里有一个告示牌，告示牌上有一个数字 $x$ ，表示从这个房间开始按逆时针方向选择第 $x$ 个有楼梯的房间（假定该房间的编号为 $k$），从该房间上楼，上楼后到达上一层的 $k$ 号房间。比如当前房间的指示牌上写着 $2$ ，则按逆时针方向开始尝试，找到第 $2$ 个有楼梯的房间，从该房间上楼。如果当前房间本身就有楼梯通向上层，该房间作为第一个有楼梯的房间。
寻宝说明书的最后用红色大号字体写着：“寻宝须知：帮助你找到每层上楼房间的指示牌上的数字（即每层第一个进入的房间内指示牌上的数字）总和为打开宝箱的密钥”。
请帮助 liu3600 算出这个打开宝箱的密钥。
输入格式
无
输出格式
无
说明/提示
【数据范围】
$1 \le N \le 10^4,1 \le M \le 100,1\le x \le 10^6$