码~农~谷~
题目：
360将用户产品分为电脑软件、手机软件、智能硬件三大类，每个大类里有一些产品，其中第 i 个大类内有 ai 个产品。每个产品均各不相同，且一个产品不会同时属于多个类别。
你现在要从中取出不超过 n 个产品进行试用，并且要求第 i 个大类中的产品至少试用 li 个，至多试用 ri 个。
问一共有多少种不同的试用产品的选取方案。因为方案数太大，只需要输出总方案数除以 47 的余数即可。
输入格式
第一行输入一个整数 T（1 ≤ T ≤ 60），表示数据组数。
接下来 T 组数据，每组数据 4 行。
前 3 行的第 i 行包含 3 个整数 ai，li，ri（1 ≤ li ≤ ri ≤ ai ≤ 1018）。
第 4 行包含一个整数 n，表示一共要试用不超过 n 个产品（1 ≤ n ≤ 1018）。
输出格式
一共输出 T 行，每行一个整数，表示总方案数除以 47 的余数。
提示信息
对于第一组数据，设第一大类中的产品分别为{A, B, C}，第二大类为{D, E}，第三大类为{F, G, H}。则方案一共有如下 12 种：
{A, B, C, D, F}{A, B, C, D, G}{A, B, C, D, H}{A, B, C, E, F}{A, B, C, E, G}{A, B, C, E, H}{A, B, C, D, F, G}{A, B, C, D, F, H}{A, B, C, D, G, H}{A, B, C, E, F, G}{A, B, C, E, F, H}{A, B, C, E, G, H}
样例
输入：
23 3 32 1 13 1 268 1 38 1 32 1 14
输出：
1237
ps：这是一道企业检测题，求教！！！（只有15人通过，看来真是不简单）