36ος ΠΔΠ Καμπ (κοινά)
tournament (tournament)

Σε ένα πρωτάθλημα online μπιλιάρδου, κάθε παίκτης παίζει με διάφορους άλλους παίκτες, με τη σειρά που ορίζει το σύστημα. Κάθε νίκη αποφέρει κάποιους βαθμούς και οι βαθμοί αυτοί αθροίζονται για κάθε παίκτη — αντίθετα οι ήττες δε δίνουν βαθμούς. Για να γίνει το παιχνίδι πιο ενδιαφέρον, οι διοργανωτές του πρωταθλήματος αποφάσισαν το εξής σύστημα βαθμολόγησης:

Οι βαθμοί κάθε νίκης αυξάνουν ανάλογα με το πλήθος των διαδοχικών νικών που έχει πετύχει ένας παίκτης. Η πρώτη νίκη δίνει \(1\) βαθμό, η δεύτερη (συνεχόμενη) \(2\) βαθμούς, η τρίτη (πάλι συνεχόμενη) \(4\) βαθμούς, η τέταρτη \(8\) βαθμούς, κ.ο.κ.
Σε περίπτωση ήττας τερματίζονται φυσικά οι διαδοχικές νίκες. Άρα, η πρώτη επόμενη νίκη θα δώσει πάλι \(1\) βαθμό.
Αν ένας παίκτης χάσει δύο συνεχόμενες φορές, τότε αποκλείεται από το πρωτάθλημα.

Έστω δύο φυσικοί αριθμοί \(A \leq B\). Βρείτε με πόσους διαφορετικούς τρόπους μπορεί ένας παίκτης να συγκεντρώσει \(K\) βαθμούς, όπου \(A \leq K \leq B\), προτού αποκλειστεί από το πρωτάθλημα.

Για παράδειγμα, έστω \(A = 2\) και \(B = 4\). Ένας παίκτης μπορεί να συγκεντρώσει \(2\), \(3\) ή \(4\) βαθμούς με τους εξής δώδεκα (\(12\)) τρόπους, όπου οι αριθμοί σημαίνουν νίκη που δίνει τόσους βαθμούς όση είναι η τιμή του αριθμού και το σύμβολο “x” σημαίνει ήττα:

1 x 1 x x
x 1 x 1 x x
1 x 1 x 1 x x
x 1 x 1 x 1 x x
1 x 1 x 1 x 1 x x
x 1 x 1 x 1 x 1 x x

1 x 1 2 x x
x 1 x 1 2 x x
1 2 x x
x 1 2 x x
1 2 x 1 x x
x 1 2 x 1 x x

Δεδομένα εισόδου (tournament.in)

Η πρώτη γραμμή της εισόδου θα περιέχει έναν ακέραιο αριθμό \(N\), το πλήθος των ερωτημάτων που πρέπει να απαντήσετε. Κάθε μία από τις επόμενες \(N\) γραμμές της εισόδου θα περιέχει δύο αριθμούς, \(A\) και \(B\), χωρισμένους με ένα κενό διάστημα.

Δεδομένα εξόδου (tournament.out)

Η έξοδος πρέπει να αποτελείται από ακριβώς \(N\) γραμμές που κάθε μία θα περιέχει ακριβώς έναν ακέραιο αριθμό: την απάντηση στο αντίστοιχο ερώτημα κατά σειρά. Επειδή για μεγάλες τιμές των \(A\) και \(B\) η απάντηση μπορεί να είναι πολύ μεγάλος αριθμός, πρέπει να τυπώνετε το υπόλοιπο (modulo) της διαίρεσης αυτού του αριθμού με \(10^9 + 7\).

Παράδειγμα αρχείων εισόδου-εξόδου:

tournament.in	tournament.out
4 2 4 3 3 17 42 1742 4217	12 4 126321690 376826466

Εξήγηση: Το πρώτο ερώτημα, με \(A = 2\) και \(B = 4\), είναι αυτό που εξηγήθηκε αναλυτικά παραπάνω.

Περιορισμοί:

\(1 \leq N \leq 1.000.000\),
\(0 \leq A \leq B \leq 1.000.000\).

Προσέξτε ότι το μέγεθος τόσο των δεδομένων εισόδου όσο και των δεδομένων εξόδου μπορεί να είναι μεγάλο. Σας συστήνουμε να διαβάσετε και να τυπώνετε τα δεδομένα με αποδοτικό τρόπο (βλ. <cstdio> και scanf/printf).

Subtasks

Για περιπτώσεις ελέγχου συνολικής αξίας 20%, θα είναι \(Ν \leq 1.000\) και \(B \leq 30\).
Για περιπτώσεις ελέγχου συνολικής αξίας 50%, θα είναι \(N \leq 10.000\) και \(B \leq 100.000\).
Για περιπτώσεις ελέγχου συνολικής αξίας 60%, θα είναι \(B - A \leq 10\).