문제
1번부터 N번까지 번호가 매겨져 있는 N개의 마을과 마을을 연결하는 M개의 일방통행 도로로 이루어진 나라가 있다. 이 나라에서는 자전거 경주 대회를 개최하려고 한다. 경주는 1번 마을에서 시작해야 하고, 2번 마을에서 끝나야 한다.
자전거 경주를 개최할 수 있는 경로의 수는 총 몇 가지가 있는지 구하는 프로그램을 작성하시오.
출력
첫째 줄에 가능한 자전거 경주 대회 경로의 수를 출력한다. 수가 9자리를 넘어가는 경우에는 뒤의 9자리만 출력하면 된다. 만약, 경로의 수가 무한대인 경우에는 "inf"를 출력한다.
W3sicHJvYmxlbV9pZCI6IjMwNDQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM3OTBcdWM4MDRcdWFjNzAgXHVhY2JkXHVjOGZjIFx1YzkwMFx1YmU0NFx1ZDU1OFx1YWUzMCIsImRlc2NyaXB0aW9uIjoiPHA+MVx1YmM4OFx1YmQ4MFx1ZDEzMCBOXHViYzg4XHVhZTRjXHVjOWMwIFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWI5ZTRcdWFjYThcdWM4MzggXHVjNzg4XHViMjk0IE5cdWFjMWNcdWM3NTggXHViOWM4XHVjNzQ0XHVhY2ZjIFx1YjljOFx1Yzc0NFx1Yzc0NCBcdWM1ZjBcdWFjYjBcdWQ1NThcdWIyOTQgTVx1YWMxY1x1Yzc1OCBcdWM3N2NcdWJjMjlcdWQxYjVcdWQ1ODkgXHViM2M0XHViODVjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWIwOThcdWI3N2NcdWFjMDAgXHVjNzg4XHViMmU0LiBcdWM3NzQgXHViMDk4XHViNzdjXHVjNWQwXHVjMTFjXHViMjk0IFx1Yzc5MFx1YzgwNFx1YWM3MCBcdWFjYmRcdWM4ZmMgXHViMzAwXHVkNjhjXHViOTdjIFx1YWMxY1x1Y2Q1Y1x1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YWNiZFx1YzhmY1x1YjI5NCAxXHViYzg4IFx1YjljOFx1Yzc0NFx1YzVkMFx1YzExYyBcdWMyZGNcdWM3OTFcdWQ1NzRcdWM1N2MgXHVkNTU4XHVhY2UwLCAyXHViYzg4IFx1YjljOFx1Yzc0NFx1YzVkMFx1YzExYyBcdWIwNWRcdWIwOThcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3OTBcdWM4MDRcdWFjNzAgXHVhY2JkXHVjOGZjXHViOTdjIFx1YWMxY1x1Y2Q1Y1x1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YWNiZFx1Yjg1Y1x1Yzc1OCBcdWMyMThcdWIyOTQgXHVjZDFkIFx1YmE4NyBcdWFjMDBcdWM5YzBcdWFjMDAgXHVjNzg4XHViMjk0XHVjOWMwIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBOXHVhY2ZjIE1cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMiAmbGU7IE4gJmxlOyAxMCwwMDAsIDEgJmxlOyBNICZsZTsgMTAwLDAwMCk8XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIE1cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YjNjNFx1Yjg1Y1x1Yzc1OCBcdWM4MTVcdWJjZjRcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IEFcdWM2NDAgQlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NCBcdWM4MTVcdWJjZjRcdWIyOTQgQVx1YzVkMFx1YzExYyBCXHViODVjIFx1ZDVhNVx1ZDU1OFx1YjI5NCBcdWIzYzRcdWI4NWNcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI0NTAgXHViOWM4XHVjNzQ0XHVjNzc0IFx1ZDU1OFx1YjA5OCBcdWM3NzRcdWMwYzFcdWM3NTggXHViM2M0XHViODVjXHViODVjIFx1YzVmMFx1YWNiMFx1YjQxOFx1YzViNCBcdWM3ODhcdWM3NDQgXHVjMjE4XHViM2M0IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWM3OTBcdWM4MDRcdWFjNzAgXHVhY2JkXHVjOGZjIFx1YjMwMFx1ZDY4YyBcdWFjYmRcdWI4NWNcdWM3NTggXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVjMjE4XHVhYzAwIDlcdWM3OTBcdWI5YWNcdWI5N2MgXHViMTE4XHVjNWI0XHVhYzAwXHViMjk0IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBcdWI0YTRcdWM3NTggOVx1Yzc5MFx1YjlhY1x1YjljYyBcdWNkOWNcdWI4MjVcdWQ1NThcdWJhNzQgXHViNDFjXHViMmU0LiBcdWI5Y2NcdWM1N2QsIFx1YWNiZFx1Yjg1Y1x1Yzc1OCBcdWMyMThcdWFjMDAgXHViYjM0XHVkNTVjXHViMzAwXHVjNzc4IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCAmcXVvdDtpbmYmcXVvdDtcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjMwNDQiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJCSUNJS0xJIiwiZGVzY3JpcHRpb24iOiI8cD5BIGJpY3ljbGUgcmFjZSBpcyBiZWluZyBvcmdhbml6ZWQgaW4gYSBsYW5kIGZhciwgZmFyIGF3YXkuIFRoZXJlIGFyZSBOIHRvd24gaW4gdGhlIGxhbmQsIG51bWJlcmVkIDEgdGhyb3VnaCBOLiBUaGVyZSBhcmUgYWxzbyBNIG9uZS13YXkgcm9hZHMgYmV0d2VlbiB0aGUgdG93bnMuIFRoZSByYWNlIHdpbGwgc3RhcnQgaW4gdG93biAxIGFuZCBlbmQgaW4gdG93biAyLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Ib3cgbWFueSBkaWZmZXJlbnQgd2F5cyBjYW4gdGhlIHJvdXRlIGJlIHNldD8gVHdvIHJvdXRlcyBhcmUgY29uc2lkZXJlZCBkaWZmZXJlbnQgaWYgdGhleSBkbyBub3QgdXNlIHRoZSBleGFjdCBzYW1lIHJvYWRzLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdHdvIGludGVnZXJzIE4gYW5kIE0gKDImbmJzcDsmbGU7IE4gJmxlOyAxMCAwMDAsIDEgJmxlOyBNICZsZTsgMTAwIDAwMCksIHRoZSBudW1iZXIgb2YgdG93bnMgYW5kIHJvYWRzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBuZXh0IE0gbGluZXMgY29udGFpbnMgdHdvIGRpZmZlcmVudCBpbnRlZ2VycyBBIGFuZCBCLCByZXByZXNlbnRpbmcgYSByb2FkIGJldHdlZW4gdG93bnMgQSBhbmQgQi4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VG93bnMgbWF5IGJlIGNvbm5lY3RlZCBieSBtb3JlIHRoYW4gb25lIHJvYWQuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IHRoZSBudW1iZXIgb2YgZGlzdGluY3Qgcm91dGVzIHRoYXQgY2FuIGJlIHNldCBvbiBhIHNpbmdsZSBsaW5lLiBJZiB0aGF0IG51bWJlciBoYXMgbW9yZSB0aGFuIG5pbmUgZGlnaXRzLCBvdXRwdXQgb25seSB0aGUgbGFzdCBuaW5lIGRpZ2l0cyBvZiB0aGUgbnVtYmVyLiBJZiB0aGVyZSBhcmUgaW5maW5pdGVseSBtYW55IHJvdXRlcywgb3V0cHV0ICZxdW90O2luZiZxdW90Oy4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d