My Number

Time Limit : 2 sec, Memory Limit : 262144 KB

A: マイナンバー - My Number -

問題

いっけなーい!遅刻遅刻!

あっ!私、今日から憧れのこの会社で働くことになったんだ!

それなのに、初日から寝坊だなんて…!?

今日は会社にマイナンバーを教えなければならない大切な日なのに…!

みんな知っていると思うけれど、一応マイナンバーの説明をするね!

マイナンバーは行政手続きにおける個人を識別するために用いられる 12 桁からなる数字列 (P_{11} P_{10} P_{9} ... P_{1} P_{0}) である。

末尾の P_{0} はチェックディジットと呼ばれ、 総務省令第八十五号第五章 に定められているように、次式で定義される。

  • 11 − ( ({\rm Σ}_{n = 1}^{11} P_{n} × Q_{n}) を 11 で除した余り )
  • ただし、 ( ({\rm Σ}_{n = 1}^{11} P_{n} × Q_{n}) を 11 で除した余り ) \≤ 1 の場合は 0 とする。

ここで、 Q_{n} (n = 1, 2, ..., 11) は次のように定義される。

  • 1 \≤ n \≤ 6 のとき n + 1
  • 7 \≤ n \≤ 11 のとき n − 5

分かったかな?

でも、12桁の数字列なんて覚えられないから、家を出る直前にマイナンバーの通知書の写真を撮ったんだ!

ほら、私のマイナンバーかっこいいでしょ!

…ってあれ?

なんでマイナンバーの上に納豆の粒が乗っているの!?

これじゃあ、1桁だけ分からなくてマイナンバーを教えられないよ!

私、これからどうなっちゃうの…!?

そうだ!

チェックディジットの定義に矛盾しないような数字を見つければいいんだ!

でも計算難しい…

ねえ、私の初日を失敗しないために、分からない数字を見つけるのを手伝って!?

えっ?

何を言っているか分かりにくかったって?

やってほしいことは要するに、

1桁だけ数字が不明な12桁のマイナンバーが与えられるので、チェックディジットの定義に矛盾しないように、不明な桁の数字を求めよ。

ただし、そのような数字が複数あるときには “MULTIPLE” と出力せよ。

ということだよ!

よろしくねっ!

入力形式

入力は、12文字の文字列 S = P_{11} P_{10} P_{9} ... P_{1} P_{0} と1個の改行がこの順番に与えられる。 P の添字が降順に付けられていることに注意せよ。 この文字列の各文字は “0”, “1”, “2”, “3”, “4”, “5”, “6”, “7”, “8”, “9”, “?” のいずれかである。 “?” は不明な桁を表し、他の文字はマイナンバーの数字を表す。 また、 “?” は S の中でちょうど1回だけ現れる。 なお、入力において、不明な桁に入る数字で、チェックディジットの定義に矛盾しないようなものが1つ以上存在することが保証される。

出力形式

不明な桁に入る数字で、チェックディジットの定義を矛盾しないようなものが唯1つに定まるときは、その数字を出力せよ。 矛盾しないような数字が複数存在するときには、 “MULTIPLE” と出力せよ。 いずれの場合も、最後に1度だけ改行せよ。

入力例1

?12345678901

出力例1

4

チェックディジットの定義より “?” が 4 以外になることはあり得ません。

入力例2

2016030810?0

出力例2

MULTIPLE

“?” が 0, 6 のいずれの場合でもチェックディジットの定義を満たします。

入力例3

20160308100?

出力例3

0

入力例4

0012300?0450

出力例4

8

Source: Ritsumeikan University Programming Camp 2016 , Day 3, Shiga, Japan, 2016-03-08