import re
import sys
def is_proper_roman_numeral(s):
return re.fullmatch('(?xi)'
'(?=[MDCLXVI])'
'(?P<thousands> M{,3})'
'(?P<hundreds>D?C{,3}|CM|CD)'
'(?P<tens> L?X{,3}|XC|XL)'
'(?P<units> V?I{,3}|IX|IV)', s)
for line in sys.stdin:
line = line.strip()
NOT = " NOT" * (not is_proper_roman_numeral(line))
print("{line!r} is{NOT} valid".format(**vars()))
aW1wb3J0IHJlCmltcG9ydCBzeXMKCmRlZiBpc19wcm9wZXJfcm9tYW5fbnVtZXJhbChzKToKICAgICByZXR1cm4gcmUuZnVsbG1hdGNoKCcoP3hpKScKICAgICAgICAgJyg/PVtNRENMWFZJXSknCiAgICAgICAgICcoP1A8dGhvdXNhbmRzPiBNeywzfSknCiAgICAgICAgICcoP1A8aHVuZHJlZHM+RD9DeywzfXxDTXxDRCknCiAgICAgICAgICcoP1A8dGVucz4gICAgTD9YeywzfXxYQ3xYTCknCiAgICAgICAgICcoP1A8dW5pdHM+ICAgVj9JeywzfXxJWHxJViknLCBzKQoKZm9yIGxpbmUgaW4gc3lzLnN0ZGluOgogICAgbGluZSA9IGxpbmUuc3RyaXAoKQogICAgTk9UID0gIiBOT1QiICogKG5vdCBpc19wcm9wZXJfcm9tYW5fbnVtZXJhbChsaW5lKSkKICAgIHByaW50KCJ7bGluZSFyfSBpc3tOT1R9IHZhbGlkIi5mb3JtYXQoKip2YXJzKCkpKQ==