Description

给定长度为 $n$ 的 01 串 $c$, 求 二元组$(a,b)$ 的数量，其中

1. $a,b$ 是两个长度为 $n$ 的排列
2. $\forall 1\le i\le n, a_i - b_i \le c_i$

答案模$10^9+7$，多组数据。

Format

Input

第一行一个正整数$T$表示测试组数。

接下来$T$行，每行一个 01 串$c$

Output

$T$行，每行是答案

Samples

10
1101011 
1101111 
1101110 
1010111 
1011010 
0010011 
1000001 
1100110 
0100011 
1100100

103680
184320
103680
103680
57600
31680
17280
57600
31680
31680

Limitation

本题只有三个测试点(包含样例)。

$T=10$

$1<|c|\le 10^5$

$\sum |c| \le 10^6$