VMSS '15 #0 - Head Data Slave Applications

View as PDF

Submit solution


Points: 10
Time limit: 1.0s
Memory limit: 256M

Authors:
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig
Welcome to Massey CS Club 2015/16!

To start things off, a new head data slave needs to be hired (the old one has been promoted).

The new head data slave must not only be fast at copying data, but also decent with math calculations or simply bashing numbers. Luckily for most people, the head data slave exam only consists of 1 question. Solve this question for bonus (Komachi) points.

Question

In the massive multiplayer online role-playing game Elder Tale, the humans are at war with monsters. Shiroe, the strategist of the legendary Debauchery Tea Party is in charge of organizing N (1 \le N \le 500) NPC militants to fight. The armed forces consists of K different kinds of militants. Each militant is labelled with a number 1 to K based on importance. Militants who share the same number are indistinguishable. Shiroe wants to know the number of ways he can organize his army in a line such that the last militant with number i is before the last militant with number i+1 for (1 \le i \le K-1).

Input Specification

The first line of input will have one integer K (1 \le K \le 500), the number of different kinds of militants.
The following K lines will contain one integer each. The i-th line will contain m_i (1 \le m_i \le 500), the number of militants with the number i.

Output Specification

Print the number of ways Shiroe can order his armies modulo 1\,000\,000\,007.

Sample Input #1

3
2
2
1

Sample Output #1

3

Explanation

The 3 ways are:

1 1 2 2 3

1 2 1 2 3

2 1 1 2 3

Ah, that scored high Komachi points!

Sample Input #2

5
4
1
2
3
1

Sample Output #2

216


Comments


  • 2
    k_53P  commented on Sept. 17, 2015, 8:45 p.m. edited

    I was only able to get AC by outputting my answer modulo 1000000007 instead of 1000007.

    edit: it seems that the other AC solution does this too


    • 1
      FatalEagle  commented on Sept. 17, 2015, 10:22 p.m.

      Statement fixed.


    • 3
      cheesecake  commented on Sept. 17, 2015, 9:03 p.m.

      Oh wow I actually just noticed that now. I guess terrible reading comes in handy sometimes :^)


    • 2
      awaykened  commented on Sept. 17, 2015, 8:58 p.m. edited

      zzz this would have been nice to know about an hour or two ago.... nonetheless thank you for sparing me 3 more hours of debugging time


  • 0
    YouZ  commented on Sept. 17, 2015, 4:11 p.m.

    Leo I like Log Horizon and everything, but I don't get the input specifications. What are those integers supposed to mean????


    • 0
      nathanl3  commented on Sept. 20, 2015, 7:30 a.m. edited

      The given input is : 3 2 2 1

      Which is interpreted as:

      First line: There are 3 types of militants

      Second line: There are 2 militants of type 1

      Third line: There are 2 militants of type 2

      Fourth line: There are 2 militants of type 3

      For example, 1 1 2 2 3 is a valid case for this input