Известный коллекционер камней

Mr. B любит играть с разноцветными камнями. В его коллекции есть n цветов камней, причем два камня одного цвета неразличимы. Mr. B хочет выбрать несколько камней и выстроить их в ряд, чтобы создать красивый узор. После нескольких попыток он обнаруживает, что ему сложно перечислить все возможные узоры. Поэтому он просит вас написать программу, которая подсчитает количество различных возможных узоров.

Два узора считаются различными, если они отличаются по количеству камней или хотя бы один камень в них имеет другой цвет.

Входные данные

Каждый тестовый случай начинается с строки, содержащей целое число n, обозначающее количество видов камней у Mr. B. Затем следует строка из n целых чисел, представляющих количество доступных камней каждого цвета. Все входные числа неотрицательны и не превышают 100.

Выходные данные

Для каждого тестового случая выведите строку с номером случая и количеством различных узоров, которые Mr. B может создать из этих камней, по модулю 1000000007, который является простым числом.

Примеры

Примечание

В первом случае, предположим, что цвета камней у Mr. B обозначены как B, G и M. Различные узоры, которые Mr. B может составить, это: B; G; M; BG; BM; GM; GB; MB; MG; BGM; BMG; GBM; GMB; MBG; MGB.