Algorithms and Data Structures

Profound Academy

Course Status
1
🛠️ Implementation
2
0️⃣ Binary Numbers
3
🔟 Bitwise operations
4
🔟 Extracurricular Bitwise operations
5
🔟 Recap
6
➕ Prefix Sums
7
➕ Extracurricular Prefix sum
8
🪟 Sliding window / Two pointers
9
🪟 Recap
10
⏲️ Modular Arithmetic
11
🔢 Number Theory
12
🔢 Extracurricular Number Theory
13
🔍 Binary Search
14
🔍 Extracurricular Binary Search
15
🔍 Recap
16
📶 Basic Sorting
17
📶 Extracurricular Sorting
18
🤑 Greedy Algorithms
19
🤑 Extracurricular Greedy
20
🧨 Basic Dynamic Programming
21
🧨 Extracurricular Dynamic Programming
22
🔄 Recursion
23
🔄 Extracurricular Recursion
24
🪓 Divide & Conquer + Advanced Sorting
25
🪓 Extracurricular Divide and Conquer
26
🪓 Recap
27
🔗 Linked LIst
28
📚 Queue & Stack
29
📚 Extracurricular Queue and Stack
30
🌲 Binary tree and BST
31
🌲 Extracurricular Binary Tree and BST
32
🗼 Heap
33
🗼 Extracurricular Heap
34
#️⃣ Hashing
35
#️⃣ Extracurricular Hashing
36
💣 Advanced Dynamic Programming
37
🔆 Graph Representation
38
🔆 Extracurricular Graph Representation
39
🕸️ BFS
40
🕸️ Extracurricular BFS
41
☸️ DFS
42
☸️ Extracurricular DFS
43
🔱 Trie
44
🔱 Extracurricular Trie
45
🏋‍♂ Dijkstra
46
🏋‍♂ Extracurricular Dijkstra
47
↩️ Backtracking
48
↩️ Extracurricular Backtracking
49
🎄 Segment Tree
50
🎄 Extracurricular Segment Tree

Number of paths in a grid

Given a grid of height h and width w, you are asked to calculate the number of unique paths one can take to move from the top-left corner to the bottom-right corner. You’re only allowed to move right and down.

o	➡️	ㅤ	ㅤ
⬇️	ㅤ	ㅤ	ㅤ
ㅤ	ㅤ	ㅤ	x

Input

The input contains two integers h and w (1 ≤ h, w ≤ 100).

Output

The program should print the number of unique paths it’s possible to take from the top-left to the bottom-right corner of the grid. The output can be large, so the answer should be taken modulo .

Examples

Input	Output
2 3	3
3 4	10
7 3	28

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in

Sign in to continue