문제

N-beat is a popular rhythm arcade game, in which you push buttons arranged in a x*y grid. The buttons light up when you have to push them; you have to push them with precise timing to get scores.

One game of N-beat consists of one or more screens. A screen is a configuration of lit buttons which you have to push.

For example, the picture above shows 4 successive screens for a N-beat machine with 4*4 grid. Here, boxes with the target mark are the lit buttons you have to press.

A sequence of screens in a game is called a transcription.

Now, Jaeha Koo, a genius composer, just made a new song for N-beat. You're going to make transcription for this song.

There are B beats in this song, so this transcription will consist of B screens. Therefore, without any restriction, there are a total of (2^(x*y))^B possible transcriptions.

But transcriptions differ in difficulty. Generally, you can push one button with one finger, so it's harder when a single screen has more lit buttons. Especially, if a screen has more than 10 lit buttons, it's very difficult to push them successfully. Also, adjacent screens having a lot of lit buttons can also can make the game difficult. For example, two successive screens with 7 and 6 lit buttons each might be more difficult than two screens with 2 and 8 lit buttons each.

As a generous transcriptor, you decided to limit the number of lit buttons. The limit is given as three nonnegative integers: p₁, p₂, and p₃. p₁ is the maximum number of lit buttons you can have in any one screen. p₂ is the maximum number of lit buttons you can have in any two consecutive screens. Also, as you guessed, p₃ is the maximum number of lit buttons you can have in any three consecutive screens. In the picture above, 4 screens each have 4, 8, 6, 8 of turned-on buttons, so this transcription will only be valid if p₁ >= 8, p₂ >= 14, and p₃ >= 22.

Your task is to calculate the number of possible transcriptions given x, y, B, p₁, p₂ and p₃. As the result can be quite huge, just calculate the answer MOD 10⁹+7.