题目描述

小H为了完成一篇论文，一共要完成 $n$ 个实验。其中第 $i$ 个实验需要 $a_i$ 的时间去完成。小H可以同时进行若干实验，但存在一些实验，只有当它的若干前置实验完成时，才能开始进行该实验。同时我们认为小H在一个实验的前置实验都完成时，就能马上开始该实验。

为了让小H尽快完成论文，需要知道在最优的情况下，最后一个完成的实验什么时候完成？小H还想知道，在保证最后一个实验尽快完成的情况下（即保证上一问的答案不变），他想知道每个实验最晚可以什么时候开始。

设第 $i$ 个实验最早可能的开始时间为 $f_i$，不影响最后一个实验完成时间的最晚开始时间为 $g_i$，请你回答除以 $10^9+7$ 所得的余数，题目保证有解。