SP7386 ACTIV - Activities

Ana 兴趣广泛，喜欢杂技、炼金术、射箭、艺术、阿拉伯舞蹈等等。为此，她加入了一个提供多种课程的俱乐部。每门课程在每周都有固定的时间段。Ana 希望报名尽可能多的课程，但由于时间上有重叠，所以她想找出一组不重叠的课程来参加。我们认为，如果一组课程中没有任意两门的时间重叠，那么这组课程就是不重叠的。如果一门课程的开始时间与另一门课程的结束时间相同，这种情况不视为重叠。 Ana 决定列出所有不重叠且非空的课程组合。然后，她将选择她最喜欢的那一组。为了预测写下这些组合所需的纸张量，她希望你能帮她计算一共有多少这样的组合。

每个测试用例由多行组成。第一行包含一个整数 $N$，表示俱乐部提供的课程数量（$1 \leq N \leq 10^5$）。接下来的 $N$ 行中，每行包含两个整数 $S$ 和 $E$，表示课程的开始时间和结束时间（$1 \leq S < E \leq 10^9$）。输入以一个单独的 $-1$ 终止。

对于每个测试用例，输出一行，表示不重叠且非空的课程组合的数量。为了简化问题，只需输出结果的最后 8 位数字。如果结果少于 8 位数字，请在前面补零以达到 8 位。 **本翻译由 AI 自动生成**