Відомий колекціонер каменів

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.