{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003chtml\u003e\n \u003chead\u003e\u003c/head\u003e\n \u003cbody\u003e\n \u003cdiv\u003e\n In ICPCCamp, there are only three capitals -- \n \u003cem\u003eAlpha\u003c/em\u003e, \n \u003cem\u003eBeta\u003c/em\u003e and \n \u003cem\u003eGamma\u003c/em\u003e. There are also \n \u003cstrong\u003ea \u003c/strong\u003ebidirectional roads between capitals \n \u003cem\u003eAlpha \u003c/em\u003eand \n \u003cem\u003eBeta\u003c/em\u003e, \n \u003cstrong\u003eb \u003c/strong\u003eroads between \n \u003cem\u003eAlpha \u003c/em\u003eand\u0026nbsp;\n \u003cem\u003eGamma\u003c/em\u003e, and \n \u003cstrong\u003ec \u003c/strong\u003eroads between \n \u003cem\u003eBeta \u003c/em\u003eand \n \u003cem\u003eGamma\u003c/em\u003e.\n \u003c/div\u003e \n \u003cdiv\u003e\n Bobo lives in capital \n \u003cem\u003eAlpha \u003c/em\u003eand would like to travel around ICPCCamp. He will start from capital \n \u003cem\u003eAlpha\u003c/em\u003e, travel along each road exactly once, and return back to capital \n \u003cem\u003eAlpha\u003c/em\u003e.\n \u003c/div\u003e \n \u003cdiv\u003e\n It is clear that Bobo has many plans to choose from. He would like to find out the number of different plans, modulo (10\n \u003csup\u003e9\u003c/sup\u003e+7).\n \u003c/div\u003e \n \u003cdiv\u003e\n Note that two plans \n \u003cstrong\u003eA \u003c/strong\u003eand \n \u003cstrong\u003eB \u003c/strong\u003eare considered different only if there exists an \n \u003cstrong\u003ei \u003c/strong\u003ewhere the \n \u003cstrong\u003ei\u003c/strong\u003e-th traveled road in plan \n \u003cstrong\u003eA \u003c/strong\u003eis different from the \n \u003cstrong\u003ei\u003c/strong\u003e-th road in plan \n \u003cstrong\u003eB\u003c/strong\u003e.\n \u003c/div\u003e \n \u003cdiv\u003e\u003c/div\u003e \n \u003cp\u003e\u003c/p\u003e\n \u003c/body\u003e\n\u003c/html\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003chtml\u003e\n \u003chead\u003e\u003c/head\u003e\n \u003cbody\u003e\n \u003cdiv\u003e\n The input contains at most 30 sets. For each set:\n \u003c/div\u003e \n \u003cdiv\u003e\n The first line contains 3 integers a,b,c (1≤a,b,c≤10\n \u003csup\u003e5\u003c/sup\u003e).\n \u003c/div\u003e \n \u003cdiv\u003e\u003c/div\u003e\n \u003c/body\u003e\n\u003c/html\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003chtml\u003e\n \u003chead\u003e\u003c/head\u003e\n \u003cbody\u003e\n \u003cdiv\u003e\n \u0026nbsp;For each set, an integer denotes the number of different ways modulo (10\n \u003csup\u003e9\u003c/sup\u003e+7).\n \u003c/div\u003e\n \u003c/body\u003e\n\u003c/html\u003e"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cpre\u003e1 1 3\r\n1 3 1\r\n100000 100000 100000\r\n\u003c/pre\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cpre\u003e12\r\n24\r\n525502296\r\n\u003c/pre\u003e"}},{"title":"Hint","value":{"format":"HTML","content":"\u003chtml\u003e\n \u003chead\u003e\u003c/head\u003e\n \u003cbody\u003e\u003c/body\u003e\n\u003c/html\u003e"}}]}