ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

ICPC UrFU Contest Qualifier 2026

About     Problems     Submit solution     Judge status     Standings
Contest is over

D. Good Enough...

Time limit: 1.0 second
Memory limit: 256 MB
Workers installed a window of width W decimeters and height H decimeters. But they forgot that it must consist of sections. As is known, the rectangular sections in any window form a grid, and two sections that are next to each other on the left and on the right (with a common side) are the same. It is also known that the width and the height of each section must be a positive integer number of decimeters, and there must be more than one section both vertically and horizontally. Below are two examples of dividing a 4 × 3 window into sections:
1 1 2 2
3 3 4 4
3 3 4 4
1 2 3 4
1 2 3 4
5 6 7 8
To avoid installing a new window with sections, the workers decided to glue horizontal and vertical divider strips onto the window, from one edge to the opposite edge, so that the window looks divided into sections. Find the number of ways to do this.

Input

The first line contains an integer W — the width of the window (2 ≤ W ≤ 106).
The second line contains an integer H — the height of the window (2 ≤ H ≤ 106).

Output

Print the number of ways to glue horizontal and vertical divider strips onto the window so that it appears to be divided into sections. Since this number may be large, print the remainder of dividing this number by 109 + 7.

Sample

inputoutput
4
3
6
Problem Author: Vadim Barinov
Problem Source: The 2026 ICPC UrFU Qualification