The problem set document for the Yokohama Chinatown Gluttony Contest was kept in a safe at the headquarters of the Kanagawa Gourmendies Foundation. It was considered to be quite secure, but, in the morning of the very day of the contest, the executive director of the foundation found that the document was missing!
The director checked that the document was in the safe when she left the headquarters in the evening of the day before. To open the door of the headquarters office, a valid ID card has to be touched on the reader inside or outside of the door. As the door and its lock are not broken, the thief should have used a valid ID card.
Normally, all the entries and exits through the door are recorded with the ID. The system, however, has been compromised somehow, and some of the recorded ID’s are lost.
It is sure that nobody was in the office when the director left, but, many persons visited the office since then to prepare the contest materials. It is sure that the same ID card was used only once for entry and then once for exit.
The director is planning inquiries to grasp all the visits during the night. You are asked to write a program that calculates the number of possible combinations of ID’s to fill the lost parts of the records.
