{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003ePicks is always lost. Therefore he bought N guideposts.\u003cbr\u003e\u003cbr\u003eThe guideposts is labeled from 1 to N. His guideposts have a thorny problem: if Picks have used the i-th guidepost, he can only use the guidepost which has a larger label than i.\u003cbr\u003e\u003cbr\u003eHe is lost again. He\u0027d like to go from city S to city T (his route just needs to ended up at city T, so he can arrive at city T and leave again).\u003cbr\u003e\u003cbr\u003eWhen Picks choose a road at a city to go to another city, he will set a guidepost on the road (There could be more than one guideposts on a road).\u003cbr\u003e\u003cbr\u003eAt the same time, he has a lucky number K. He order that the step of his route must be a multiple of K (NOTICE: the number of steps can be ZERO), since he is a obsessional person..\u003cbr\u003e\u003cbr\u003eIn this way, Picks want to know how many different method he could make to set the guideposts when he finish his route.\u003cbr\u003e\u003cbr\u003eTwo method is considered diffirent, if and only if there is a road have different guideposts.\u003c/p\u003e\u003cp\u003e\u003cbr\u003eBecause of the large answer, your task is to get the answer modulo P.\u003cimg src\u003d\"CDN_BASE_URL/e923da644dbeae7d7b0315471120be9a?v\u003d1720896537\" width\u003d\"106\" height\u003d\"23\"\u003e,P is a prime as well.\u003c/p\u003e\u003cp\u003e\u003cbr\u003e\u003c/p\u003e\u003cp\u003e\u003cstrong\u003e数据范围\u003c/strong\u003e\u003c/p\u003e\u003cp\u003e\u003cimg style\u003d\"display: block;\" src\u003d\"CDN_BASE_URL/a3998208626c59ae73834ae773cf354f?v\u003d1720896537\" width\u003d\"492\" height\u003d\"62\"\u003e\u003c/p\u003e\u003cp\u003e\u003cbr\u003e\u003c/p\u003e\u003cp\u003e\u003cstrong\u003e样例解释（图）\u003c/strong\u003e\u003c/p\u003e\u003cp\u003e\u003cimg src\u003d\"CDN_BASE_URL/a59f0f2fc5afbb02c897d8d003a3bf2b?v\u003d1720896537\" width\u003d\"135\" height\u003d\"136\"\u003e\u003cbr\u003e\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"There are multiple tests ( no more than 10 ). For each test:\u003cbr\u003e\u003cbr\u003eThe first line contains four numbers: M, N, K, P. M is the number of cities. N is the amount of the guideposts. K is Picks\u0027 lucky number. P is the modular number.\u003cbr\u003e\u003cbr\u003eThe second line contains three numbers: L, S, T. L is the number of the road. S, T is the launch pad and the target.\u003cbr\u003e\u003cbr\u003eThe i-th line of the next L lines, contains two numbers: u[i], v[i]. It means the i-th road is from city u[i] to city v[i] (road is one-way road)."}},{"title":"Output","value":{"format":"HTML","content":"For each test:\u003cbr\u003e\u003cbr\u003eThe answer modulo P."}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3 4 2 103\r\n3 1 3\r\n1 2\r\n2 3\r\n3 2\r\n3 1 2 103\r\n3 1 1\r\n1 2\r\n2 3\r\n3 2\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e7\r\n1\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Hint","value":{"format":"HTML","content":"The possible method for the first example: (The i-th set means the guideposts which is set on i-th road)\u003cbr\u003e\u003cbr\u003e1. {1}, {2}, {}.\u003cbr\u003e2. {1}, {3}, {}.\u003cbr\u003e3. {1}, {4}, {}.\u003cbr\u003e4. {2}, {3}, {}.\u003cbr\u003e5. {2}, {4}, {}.\u003cbr\u003e6. {3}, {4}, {}.\u003cbr\u003e7. {1}, {2,4}, {3}."}}]}