题目描述

平面上的若干条直线会把平面分割成若干区域。对于一组直线 $L$，定义 $two(L)$ 为：这些区域中，边界恰好与 $L$ 中两条不同直线相邻的区域数量。

现给定 $n$ 条直线，第 $i$ 条直线的方程为

$a_i x+b_i y=c_i$。

所有直线均处于一般位置，保证：

• 没有直线水平或竖直；
• 任意两条直线不平行；
• 任意三条直线不共点。

对给定 $n$ 条直线的每一个子集 $L$，计算 $two(L)$，求这些值的总和，并对 $10^9+7$ 取模。

输入格式

第一行输入一个整数 $n$。

接下来 $n$ 行，每行三个整数 $a_i,b_i,c_i$，表示直线 $a_i x+b_i y=c_i$。

输出格式

输出一个整数，表示所有直线子集对应的 $two(L)$ 之和对 $10^9+7$ 取模的结果。

数据范围

• $2\le n\le1000$；
• $-10000\le a_i,b_i,c_i\le10000$；
• $a_i\ne0$ 且 $b_i\ne0$；
• 输入满足题目所述的一般位置条件。