Unbeknownst to Farmer John, Bessie is quite the patron of the arts! Most recently, she has begun studying many of the great poets, and now, she wants to try writing some poetry of her own.

Bessie knows N (1 \leq N \leq 5000) words, and she wants to arrange them into poems. Bessie has determined the length, in syllables, of each of her words, and she has also assigned them into "rhyme classes". Every word rhymes only with other words in the same rhyme class.

Bessie's poems each include M lines (1 \leq M \leq 10^5), and each line must consist of K (1 \leq K \leq 5000) syllables. Moreover, Bessie's poetry must adhere to a specific rhyme scheme.

Bessie would like to know how many different poems she can write that satisfy the given constraints.

Problem credits: Jay Leeds

#4096 upload 3 done 1 how_to_reg 1

Cow Poetry timer 2s memory 512MB

#4096

Cow Poetry 2s 512MB