{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eJaber loves video games, his favorite game is DS:GO, unfortunately he\u0027s very bad at it, that\u0027s why he decided to quit competitive programming and train for DS:GO instead.\u003c/p\u003e\u003cp\u003eMaps in DS:GO can be seen as a grid with $$$n$$$ rows and $$$m$$$ columns, Jaber believed that in order to get better he have to fully explore the maps of the game, so he decided to build a strategy for exploring the maps.\u003c/p\u003e\u003cp\u003eIn order to build a strategy, for each cell in the map except for the bottom right cell he labels it either with a go right sign $$$\\rightarrow$$$ or a go down sign $$$\\downarrow$$$, so a strategy can be described as a grid with $$$\\rightarrow$$$ and $$$\\downarrow$$$ sings(note that he chooses all the signs in the bottom row as $$$\\rightarrow$$$ and all the signs in the rightmost column as $$$\\downarrow$$$).\u003c/p\u003e\u003cp\u003eTo fully explore the map using a strategy he picks a cell, then start the game in that cell, then move using the signs($$$\\rightarrow$$$ for right and $$$\\downarrow$$$ for down) until reaching the bottom right cell, after that if he visited all cells then he\u0027s done training with this map, otherwise he picks another cell, then restarts the game in that cell, repeating that until all cells are visited.\u003c/p\u003e\u003cp\u003eJaber want\u0027s to explore maps as fast as possible, that\u0027s why when using a strategy he always chooses the starting cells such that he restarts the game minimum number of times. Now Jaber is wondering how many strategies are there such that the minimum number of times he will start the game is exactly $$$x$$$, since Jaber quit competitive programming, he gave this task to you, calculate the answer module $$$10^9+7$$$.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eA single line containing three space separated integers $$$n,m,x$$$($$$1\\le n,m \\le 100, 1 \\le x \\le nm$$$).\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eA single integer containing the answer module $$$10^9+7$$$.\u003c/p\u003e"}},{"title":"Examples","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\u003e2 3 3\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"","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 3 9\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003eIn the first example, the following are the 2 strategies.\u003c/p\u003e\u003ccenter\u003e \u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/79dfdf89c81cd031f3dafdac7c4f746d?v\u003d1714581051\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e \u003c/center\u003e"}}]}