Huge Products

Time limit1sMemory limit512 MB

Summary

Given how many copies of each integer from 1 to 10 are available, count the distinct products of subsets, modulo 10^9+7.

Level: Medium7 of 10
Topics: Number theory, Math, Combinatorics
Solved: No attempts yet

Problem

Bobo has a lot of integers. Specifically, he has $a_1$ copies of 1, $a_2$ copies of 2, $\dots$ , and $a_{10}$ copies of 10.

Today, Bobo wants to pick some of these numbers and calculate their product. If he picks none, the product is defined as 1. Bobo wants to know how many different products he can obtain, modulo $10^9 + 7$ .

Input

Ten integers $a_1, a_2, \dots, a_{10}$ ( $0 \leq a_i \leq 10^9$ ) are given on a single line.

Output

Print a single integer: the number of different products, modulo $10^9 + 7$ .

Examples2

Example 1
Input
```
0 1 0 1 0 0 0 1 0 0
```
Expected output
```
7
```

Example 2

Input

0 1000000000 100000000 0 0 0 0 0 0 0

Expected output

400000001