Jessica zeta and Fields
All submissions for this problem are available.Cities in NY are $M$x$N$ rectangles. Killgrave is back in town and trying to mind control the whole city using his MC seeds. Jessica Jones has come to the rescue and thought of building immune walls in the city such that the effect of seeds do not propagate beyond to the walls. Since after building the walls the city is divided into different sections, so now Killgrave has to plant seeds in each section of the city. Only one seed is enough in a section to control the whole section BUT he can plant as many seeds as he wants in it. Now Jesscia has contacts and from that she knows that Killgarve has exactly '$S$' MC seeds and she also knows that he will plant all of them. Now Jessica wants to find out the Probability of Killgrave controlling the all sections successfully if he plants the seeds randomly in each section. Since this is too much information she asks zeta for help. zeta tells her that the probability will be of the form $P/Q$ where $P$ and $Q$ are both coprimes.So help the to find out $PQ$-1 modulo 1000000007 ($10^9 + 7$). $Note:$ 1.)All Seeds are Identical. 2.) Position of bomb in a particular section does not matter, just the count matters. i.e killgrave can plant the bomb in any rectangle of a particular section and cases would be considered the same. For 2 cases to be different the count of bombs in at least one section should be different, their position in a particular section does not matter. ###Input: - first line of input contains three space-separated integers $S, M, N$ - Next lines will contain a matrix of size $M$x$N$ with each element as either 0 or 1, where 1 means a wall ###Output: output a single line the probability $PQ$-1 modulo 1000000007 as described above. ###Constraints - $1 \leq S \leq 5*10^5$ - $1 \leq M \leq 10^3$ - $1 \leq N \leq 10^3$ ###Sample Input: 4 3 3 0 1 0 1 1 1 0 1 0 ###Sample Output: 628571433 ###Explanation there are four section in the city all in the corners, so there is one way to plant seeds in all section i.e. plant one seed in all sections, and the total possible ways to plant seeds anywhere in the city is $7C3=35$. so probability =1/35.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, COB, FS|
Fetching successful submissions