Скоро день рождения Piegirl, поэтому Pieguy решил купить ей букет цветов и корзинку шоколадок.
В цветочном магазине есть F различных видов цветов. Цветы i-го типа всегда имеют pi лепестков. Pieguy решил купить букет из ровно N цветов. Он может покупать цветы одного и того же типа несколько раз. Все N цветов составят букет. Важным обстоятельством является позиция цветка в букете. Вы можете считать, что букет — это упорядоченный список типов цветов.
Шоколадный магазин продает шоколад в коробках. Всего есть B различных видов коробок. В коробке i-го типа находятся ci кусочков шоколада. Pieguy может купить сколько угодно коробок, в том числе несколько одного типа. Затем он положит все коробки в корзинку, при этом важен порядок. Вы можете считать, что корзинка описывается упорядоченным списком типов коробок.
Pieguy знает, что Piegirl любит отрывать лепесток с цветка перед тем, как съесть кусочек шоколадки. Он хочет быть уверен, что она съест последний кусочек шоколадки из последней коробки сразу после того, как оторвет последний лепесток с последнего цветка. Другими словами, общее число лепестков в букете должно равняться общему числу кусочков шоколада в корзинке.
Сколько различных комбинация букета и корзинки может купить Pieguy? Отрет может быть большим, поэтому выведите его по модулю 1000000007 = 109 + 7.
Выходные данные
Выведите число комбинаций букета и корзинки, которые может купить Pieguy по модулю 1000000007 = 109 + 7.
Примечание
В первом примере есть 1 способ сделать букет с 9 лепестками (3 + 3 + 3), и 1 способ сделать корзинку с 9 кусочками шоколада (3 + 3 + 3), итого 1 комбинация. Есть 3 способа сделать букет с 13 лепестками (3 + 5 + 5, 5 + 3 + 5, 5 + 5 + 3), и 5 способов сделать корзинку с 13 кусочками шоколада (3 + 10, 10 + 3, 3 + 3 + 7, 3 + 7 + 3, 7 + 3 + 3), что дает еще 15 комбинаций. Кроме того, если 1 способ сделать букет с 15 лепестками (5 + 5 + 5) и 1 способ сделать корзинку с 15 кусочками шоколада (3 + 3 + 3 + 3 + 3), что дает еще 1 комбинацию.
Обратите внимание, что возможно существование нескольких типов цветов с одинаковым количеством лепестков. Такие типы все равно считаются различными. Аналогично, разные типы коробок тоже могут содержать равное число кусочков шоколада, но они считаются различными.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 3 3
3 5
10 3 7
|
17
|
|
2
|
6 5 10
9 3 3 4 9 9
9 9 1 6 4
|
31415926
|