훌륭한 자연경관을 가지고 있어서 관광객이 많이 오는 A산에 강이 흐르는데, 강줄기에 N개의 시설이 있다. (강줄기가 갈라져 있을 수 있다.)

이 시설들을 편의상 1번~N번으로 번호를 붙이자.

각각의 시설들은 총 F가지(식당, 생태체험관 등등)의 특징으로 분류된다.

A산의 관광 컨텐츠를 개발하는 담당을 맡은 지헌이는 강줄기를 따라 래프팅을 하면서 이동하는 방식의 새로운 이동수단을 개발했다.

지헌이의 아이디어가 A산에 적용되었다.

하지만 강물은 위에서 아래로만 흐르기 때문에 한 시설에서 래프팅 보트를 타면 무조건 특정한 다른 시설로 가게 된다.

단, 1번 시설은 강의 최하류에 위치해 있기 때문에 1번 시설에서는 어디로도 더 이상 갈 수 없고, 또한 어떤 시설에서도 1번 시설로 갈 수 있다.

요즘 들어서 여행 계획을 짜는 사람들이 많아지고 있는데, M명의 사람들은 각각 특징이 Si인 시설에서 특징이 Ei인 시설로 가고 싶어한다.

A산의 강줄기가 상당히 복잡하기 때문에, 지헌이는 특징이 Si인 시설에서 특징이 Ei인 시설로 갈 수 있는 방법의 수를 계산하는 것에 무리가 생겼고,

프로그래머인 당신에게 이를 계산하는 프로그램을 짜달라고 부탁을 하였다.

강줄기 timer 10초 memory 256MB

강줄기 10초 256MB